A minimal periods algorithm with applications

DOI10.1007/978-3-642-13509-5_6zbMATH Open1286.68536arXiv0911.3355OpenAlexW3123034202MaRDI QIDQ3575236FDOQ3575236

Authors: Zhi Xu 

Publication date: 26 July 2010

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Abstract: Kosaraju in ``Computation of squares in a string briefly described a linear-time algorithm for computing the minimal squares starting at each position in a word. Using the same construction of suffix trees, we generalize his result and describe in detail how to compute in O(k|w|)-time the minimal k-th power, with period of length larger than s, starting at each position in a word w for arbitrary exponent $kgeq2$ and integer $sgeq0$. We provide the complete proof of correctness of the algorithm, which is somehow not completely clear in Kosaraju's original paper. The algorithm can be used as a sub-routine to detect certain types of pseudo-patterns in words, which is our original intention to study the generalization.

Full work available at URL: https://arxiv.org/abs/0911.3355

Recommendations

• Extracting powers and periods in a word from its runs structure
• scientific article; zbMATH DE number 4078831
• Linear-time computation of local periods
• Mathematical Foundations of Computer Science 2003
• New simple efficient algorithms computing powers and runs in strings

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cited In (5)

• On prefix/suffix-square free words
• The extended equation of Lyndon and Schützenberger
• Equations enforcing repetitions under permutations
• Detecting one-variable patterns
• Hide and seek with repetitions

This page was built for publication: A minimal periods algorithm with applications

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