Linear-time computation of local periods

DOI10.1016/J.TCS.2004.06.024MaRDI QIDQ703549zbMATH OpenOpenAlexDBLPWikidataFDO

Authors J.-P. Duval, Gregory Kucherov, Thierry Lecroq, A. Lefebvre, Roman 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)

Recommendations

• Mathematical Foundations of Computer Science 2003
• Partial words and the critical factorization theorem revisited
• Linear-time period computation of a string with suffix trees
• Local periods and binary partial words: an algorithm

Cites work

• scientific article; zbMATH DE number 1615297 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3827234 (Why is no real title available?)
• scientific article; zbMATH DE number 3608306 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1754624 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1875416 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• A periodicity theorem on words and applications
• Algorithms on Strings, Trees and Sequences
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal algorithm for computing the repetitions in a word
• Detecting leftmost maximal periodicities
• Fast Pattern Matching in Strings
• How many squares can a string contain?
• Linear Algorithm for Data Compression via String Matching
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Periodes et repetitions des mots du monoide libre
• Periods in strings
• Périodes locales et propagation de périodes dans un mot
• Recurrence and periodicity in infinite words from local periods
• Squares, cubes, and time-space efficient string searching
• Time-space-optimal string matching
• Two-way string-matching

Cited in

(13)

• Finding the leftmost critical factorization on unordered alphabet
• On del-robust primitive words
• Longest property-preserved common factor: a new string-processing framework
• A minimal periods algorithm with applications
• Computing longest previous factor in linear time and applications
• Extracting powers and periods in a word from its runs structure
• Simple real-time constant-space string matching
• Lazy Lempel-Ziv factorization algorithms
• Lempel-Ziv factorization powered by space efficient suffix trees
• Partial words and the critical factorization theorem revisited
• Mathematical Foundations of Computer Science 2003
• Simple real-time constant-space string matching
• Linear-time period computation of a string with suffix trees

This page was built for publication: Linear-time computation of local periods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703549)