0000000001034966

AUTHOR

Mauriana Pesaresi

showing 1 related works from this author

On the longest common factor problem

2008

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…

Discrete mathematicsSettore INF/01 - InformaticaSuffix tree[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Generalized suffix treeDAWGsuffix tree[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Data structureLongest common substring problemlaw.inventionCombinatoricsSet (abstract data type)Range (mathematics)lawLongest Common Factor ProblemSuffixLowest common ancestorMathematics
researchProduct