Efficient representation and counting of antipower factors in words
From MaRDI portal
Publication:5919279
DOI10.1007/978-3-030-13435-8_31zbMath1425.68468arXiv1812.08101OpenAlexW2904570915MaRDI QIDQ5919279
Wiktor Zuba, Wojciech Rytter, Tomasz Walen, Tomasz Kociumaka, Juliusz Straszyński, Jakub Radoszewski
Publication date: 4 December 2019
Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.08101
Analysis of algorithms (68W40) Combinatorics on words (68R15) Data structures (68P05) Algorithms on strings (68W32)
Related Items
Special issue: Selected papers of the 13th international conference on language and automata theory and applications, LATA 2019, On anti-powers in aperiodic recurrent words, Circular pattern matching with \(k\) mismatches, Efficient representation and counting of antipower factors in words, Computing the Antiperiod(s) of a String
Cites Work
- Unnamed Item
- Unnamed Item
- Extracting powers and periods in a word from its runs structure
- How many double squares can a string contain?
- How many squares can a string contain?
- Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes
- Algorithms for anti-powers in strings
- Searching of gapped repeats and subrepetitions in a word
- Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets
- Anti-powers in infinite words
- Linear time algorithms for finding and representing all the tandem repeats in a string
- A data structure for dynamic trees
- Prefix frequency of lost positions
- Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
- Online Detection of Repetitions with Backtracking
- Longest Gapped Repeats and Palindromes
- A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
- A Linear-Time Algorithm for Seeds Computation
- Computing the Antiperiod(s) of a String
- Counting Palindromes in Substrings
- The “Runs” Theorem
- Cell-probe lower bounds for dynamic problems via a new communication model
- Minimal Suffix and Rotation of a Substring in Optimal Time
- On the sorting-complexity of suffix tree construction
- Lowest common ancestors in trees and directed acyclic graphs
- Efficient representation and counting of antipower factors in words
