An efficient algorithm for the All Pairs Suffix-Prefix Problem

Dan Gusfield; Gad M. Landau; Baruch Schieber

doi:10.1016/0020-0190(92)90176-V

An efficient algorithm for the All Pairs Suffix-Prefix Problem

Dan Gusfield
, Gad M. Landau
, Baruch Schieber

Research output: Contribution to journal › Article › peer-review

73 Scopus citations

Abstract

For a pair of strings (S₁, S₂), define the suffix-prefix match of (S₁, S₂) to be the longest suffix of string S₁ that matches a prefix of string S₂. The following problem is considered in this paper. Given a collection of strings S₁, S₂,...,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²) time, for any fixed alphabet. Since the size of the input is Ω(m) and the size of the output is Ω(k²) this solution is optimal.

Original language	English (US)
Pages (from-to)	181-185
Number of pages	5
Journal	Information Processing Letters
Volume	41
Issue number	4
DOIs	https://doi.org/10.1016/0020-0190(92)90176-V
State	Published - Mar 18 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Design of algorithms
string matching
suffix tree

Access to Document

10.1016/0020-0190(92)90176-V

Cite this

@article{f866d7bc9a9945dbb6efd98089cc8779,

title = "An efficient algorithm for the All Pairs Suffix-Prefix Problem",

abstract = "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.",

keywords = "Design of algorithms, string matching, suffix tree",

author = "Dan Gusfield and \{M. Landau\}, Gad and Baruch Schieber",

note = "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].",

year = "1992",

month = mar,

day = "18",

doi = "10.1016/0020-0190(92)90176-V",

language = "English (US)",

volume = "41",

pages = "181--185",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

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 - https://www.scopus.com/pages/publications/0026836177

UR - https://www.scopus.com/pages/publications/0026836177#tab=citedBy

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 -

An efficient algorithm for the All Pairs Suffix-Prefix Problem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this