Linear-time computation of local periods

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

zbMATH Keywords

AlgorithmComplexityPeriodLocal periodString matchingWord

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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