Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem

摘要

Gusfield et al. [2,3] devised an optimal O(n + m~2) time algorithm for solving the following problem: Given m strings S~1 ,S~2,...,S~m of total length n, the all-pairs suffix-prefix matching problem is the problem of finding, for all j ≠ k with 1 ≤ j ≤ m and 1 ≤ k ≤ m, the longest suffix of S~j which is a prefix of S~k.Their algorithm uses a generalized suffix tree of the input strings.