Linear-time computation of local periods
From MaRDI portal
Publication:703549
DOI10.1016/j.tcs.2004.06.024zbMath1071.68087WikidataQ58064522 ScholiaQ58064522MaRDI QIDQ703549
Jean-Pierre Duval, Thierry Lecroq, Gregory Kucherov, Arnaud Lefebvre, Roman M. Kolpakov
Publication date: 11 January 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.024
68R15: Combinatorics on words
Related Items
Lazy Lempel-Ziv Factorization Algorithms, On del-robust primitive words, Finding the leftmost critical factorization on unordered alphabet, Extracting powers and periods in a word from its runs structure, Simple real-time constant-space string matching, Lempel-Ziv factorization powered by space efficient suffix trees, Computing longest previous factor in linear time and applications, Longest property-preserved common factor: a new string-processing framework, Partial words and the critical factorization theorem revisited, Simple Real-Time Constant-Space String Matching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Periods in strings
- An optimal algorithm for computing the repetitions in a word
- Periodes et repetitions des mots du monoide libre
- How many squares can a string contain?
- Périodes locales et propagation de périodes dans un mot
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Detecting leftmost maximal periodicities
- Time-space-optimal string matching
- Squares, cubes, and time-space efficient string searching
- An O(n log n) algorithm for finding all repetitions in a string
- A periodicity theorem on words and applications
- Linear Algorithm for Data Compression via String Matching
- Fast Pattern Matching in Strings
- Algorithms on Strings, Trees and Sequences
- Two-way string-matching
- Recurrence and periodicity in infinite words from local periods
