×

An efficient algorithm for the all pairs suffix-prefix problem. (English) Zbl 0748.68021

Summary: For a pair of strings \((S_ 1,S_ 2)\), define the suffix-prefix match of \((S_ 1,S_ 2)\) to be the longest suffix of string \(S_ 1\) that matches a prefix of string \(S_ 2\). The following problem is considered:
Given a collection of strings \(S_ 1,S_ 2,\dots,S_ k\) of total length \(m\), find the suffix-prefix match for each of the \(k(k-1)\) ordered pairs of strings. We present an algorithm that solves the problem in \(O(m+k^ 2)\) time, for any fixed alphabet. Since the size of the input is \(\Omega(m)\) and the size of the output is \(\Omega(k^ 2)\) this solution is optimal.

MSC:

68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Apostolico, A.; Iliopoulos, C.; Landau, G. M.; Schieber, B.; Vishkin, U., Parallel construction of a suffix tree with applications, Algorithmica, 3, 347-365 (1988) · Zbl 0646.68080
[2] Blum, A.; Jiang, T.; Li, M.; Tromp, J.; Yanakakis, M., Linear approximation of shortest superstrings, Proc. 23rd ACM Symp. on Theory of Computing, 328-336 (1991)
[3] Kececioglu, J.; Myers, E., A procedural interface for a fragment assembly tool, (Tech. Rept. TR 89-5 (April 1989), Computer Science Dept., University of Arizona)
[4] Kececioglu, J.; Myers, E., A robust and automatic fragment assembly system (1991), Manuscript
[5] Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast pattern matching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005
[6] (Lesk, A., Computational Molecular Biology, Sources and Methods for Sequence Analysis (1988), Oxford University Press: Oxford University Press Oxford, UK)
[7] McCreight, E. M., A space-economical suffix tree construction algorithm, J. ACM, 23, 262-272 (1976) · Zbl 0329.68042
[8] Tarhio, J.; Ukkonen, E., A greedy approximation algorithm for constructing shortest common superstrings, Theoret. Comput. Sci., 57, 131-145 (1988) · Zbl 0644.68090
[9] Tarjan, R. E., Data Structures and Network Algorithms, (CBMS-NSF Regional Conference Series in Applied Mathematics (1983), SIAM: SIAM Philadelphia, PA) · Zbl 0749.90027
[10] Turner, J., Approximation algorithms for the shortest common superstring problem, Inform. and Comput., 83, 1, 1-20 (1989) · Zbl 0679.68101
[11] Ukkonen, E., A linear time algorithm for finding approximate shortest common superstrings, Algorithmica, 5, 313-323 (1990) · Zbl 0696.68075
[12] Weiner, P., Linear pattern matching algorithm, Proc. 14th IEEE Symp. on Switching and Automata Theory, 1-11 (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.