Algorithms for anti-powers in strings (Q1641162): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Text redundancies / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Repetitions in strings: algorithms and combinatorics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Anti-power prefixes of the Thue-Morse word / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4598266 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Anti-powers in infinite words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weighted Ancestors in Suffix Trees / rank | |||
Normal rank |
Latest revision as of 23:06, 15 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for anti-powers in strings |
scientific article |
Statements
Algorithms for anti-powers in strings (English)
0 references
15 June 2018
0 references
A concatenation of \(k\) identical copies of a string of length \(m\) is a power of order \(k\) (or \(k\)-power); the integer \(m\) is its period. A concatenation of \(k\) pairwise-distinct strings of identical length \(m\) is an anti-power of order \(k\) (or \(k\)-anti-power); the integer \(m\) is its anti-period. The authors show that every string of length \(n\) contains \(\Omega\left( n^{2}/k\right) \) anti-powers of order \(k\), and they provide an algorithm that finds, for a given string \(S\) of length \(n\), the locations of all substrings of \(S\) that are \(k\)-anti-powers. The algorithm is optimal since it works in \(O(n^{2}/k)\) time and \(O(n)\) space.
0 references
anti-powers
0 references
anti-periods
0 references
algorithms
0 references
combinatorics on words
0 references