Skip to Main content Skip to Navigation
Conference papers

On the longest common factor problem

Abstract : The Longest Common Factor (LCF) of a set of strings is a well studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences analysis. This problem has been solved by Hui (2000) who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications. In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take space O(n). Our algorithm works in time O(n log a), where n is the total input size and a is the size of the alphabet. We also consider a different version of our algorithm that applies to DAWGs. In this case, we prove that the algorithm works in both time and space proportional to data DAWG's size.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620280
Contributor : Maxime Crochemore <>
Submitted on : Thursday, February 14, 2013 - 8:37:37 AM
Last modification on : Monday, October 19, 2020 - 8:26:02 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 2:45:09 AM

File

IFIP08.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620280, version 1

Citation

Maxime Crochemore, Alessandra Gabriele, Filippo Mignosi, Mauriana Pesaresi. On the longest common factor problem. 5th IFIP International Conference on Theoretical Computer Science (TCS'08), Sep 2008, United States. pp.143-155. ⟨hal-00620280⟩

Share

Metrics

Record views

338

Files downloads

365