TY - JOUR
T1 - An efficient algorithm for the All Pairs Suffix-Prefix Problem
AU - Gusfield, Dan
AU - M. Landau, Gad
AU - Schieber, Baruch
N1 - Funding Information:
Correspondence to: Professor G.M. Landau, Department of Computer Science, Polytechnic University, 333 Jay Street, Brooklyn, NY 11201, USA. Tel.: +l 718 260 3154, email: [email protected]. * Partially supported by Department of Energy grant DE-FG03-90ER60999, and NSF grant CCR-8803704. Tel.: + 1 916 752 7131, email: [email protected]. * * Partially supported by NSF grant CCR-8908286. * * * Tel.: + 1 914 945 1169, email: [email protected].
PY - 1992/3/18
Y1 - 1992/3/18
N2 - For a pair of strings (S1, S2), define the suffix-prefix match of (S1, S2) to be the longest suffix of string S1 that matches a prefix of string S2. The following problem is considered in this paper. Given a collection of strings S1, S2,...,Sk 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 + k2) time, for any fixed alphabet. Since the size of the input is Ω(m) and the size of the output is Ω(k2) this solution is optimal.
AB - For a pair of strings (S1, S2), define the suffix-prefix match of (S1, S2) to be the longest suffix of string S1 that matches a prefix of string S2. The following problem is considered in this paper. Given a collection of strings S1, S2,...,Sk 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 + k2) time, for any fixed alphabet. Since the size of the input is Ω(m) and the size of the output is Ω(k2) this solution is optimal.
KW - Design of algorithms
KW - string matching
KW - suffix tree
UR - http://www.scopus.com/inward/record.url?scp=0026836177&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026836177&partnerID=8YFLogxK
U2 - 10.1016/0020-0190(92)90176-V
DO - 10.1016/0020-0190(92)90176-V
M3 - Article
AN - SCOPUS:0026836177
SN - 0020-0190
VL - 41
SP - 181
EP - 185
JO - Information Processing Letters
JF - Information Processing Letters
IS - 4
ER -