Linear-time computation of local periods
From MaRDI portal
Publication:703549
DOI10.1016/j.tcs.2004.06.024zbMath1071.68087OpenAlexW2123234403WikidataQ58064522 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
Related Items (10)
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 ⋮ Partial words and the critical factorization theorem revisited ⋮ Simple Real-Time Constant-Space String Matching ⋮ Computing longest previous factor in linear time and applications ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Longest property-preserved common factor: a new string-processing framework ⋮ Lazy Lempel-Ziv Factorization Algorithms
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
This page was built for publication: Linear-time computation of local periods
