2002 · 44 citations · 21 references
ComputingComputer ScienceAlgorithmsCombinatoricsTheory Of ComputationAlgorithm AnalysisComputational ComplexitySearching AlgorithmsString AlgorithmsComplexityComplexity Of String AlgorithmsString SearchString SearchingSubword Representation
We propose an algorithm for finding, within a word, all pairs of occurrences of the same subword within a given distance r. The obtained complexity is O(n log r + S), where S is the size of the output. We also show how the algorithm can be modified in order to find all such pairs of occurrences separated by a given word. The solution uses an algorithm for finding all quasi-squares in two strings, a problem that generalizes the well-known problem of searching for squares.
21
On the Complexity of Finite Sequences
A. Lempel, J. Ziv · IEEE Transactions on Information Theory · 1976 · 2.7K citations
Algorithms on strings, trees, and sequences
Dan Gusfield · 1997 · 1.7K citations
A Space-Economical Suffix Tree Construction Algorithm
Edward M. McCreight · Journal of the ACM · 1976 · 1.5K citations · Full text
On-line construction of suffix trees
Esko Ukkonen · Algorithmica · 1995 · 1.5K citations