Linear-time computation of local periods

DOI10.1016/J.TCS.2004.06.024zbMATH Open1071.68087DBLPjournals/tcs/DuvalKKLL04OpenAlexW2123234403WikidataQ58064522 ScholiaQ58064522MaRDI QIDQ703549FDOQ703549

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

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
• A Linear-Time Algorithm for Seeds Computation

zbMATH Keywords

AlgorithmComplexityPeriodLocal periodString matchingWord

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

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

Cited In (13)

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