Computing Longest Common Substrings Via Suffix Arrays

Computing Longest Common Substrings Via Suffix Arrays,10.1007/978-3-540-79709-8_10,Maxim A. Babenko,Tatiana A. Starikovskaya

Computing Longest Common Substrings Via Suffix Arrays  
BibTex | RIS | RefWorks Download
Given a set of N strings of total length n over alphabet Σ one may ask to find, for each 2 ≤ K ≤ N, the longest substring β that appears in at least K strings in A. It is known that this problem can be solved in O(n) time with the help of suffix trees. However, the resulting algorithm is rather complicated (in particular, it involves answering certain least common ancestor queries in O(1) time). Also, its running time and memory consumption may depend on  . This paper presents an alternative, remarkably simple approach to the above problem, which relies on the notion of suffix arrays. Once the suffix array of some auxiliary O(n)-length string is computed, one needs a simple O(n)-time postprocessing to find the requested longest substring. Since a number of efficient and simple linear-time algorithms for constructing suffix arrays has been recently developed (with constant not depending on |Σ|), our approach seems to be quite practical.
Conference: Computer Science Symposium in Russia - CSR , pp. 64-75, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.