The longest common substring problem

摘要

Given a set D of q documents, the Longest Common Substring (LCS) problem asks, for anyrninteger 2 ≤ k ≤ q, the longest substring that appears in k documents. LCS is a well-studiedrnproblem having a wide range of applications in Bioinformatics: from microarrays to DNArnsequences alignments and analysis. This problem has been solved by Hui (2000 InternationalrnJournal of Computer Science and Engineering 15 73–76) by using a famous constant-timernsolution to the Lowest Common Ancestor (LCA) problem in trees coupled with the use ofrnsuffix trees.rnIn this article, we present a simple method for solving the LCS problem by using suffix treesrn(STs) and classical union-find data structures. In turn, we show how this simple algorithmrncan be adapted in order to work with other space efficient data structures such as thernenhanced suffix arrays (ESA) and the compressed suffix tree.