Efficient representation and counting of antipower factors in words

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

zbMATH Keywords

antipower\( \alpha \)-gapped repeatrun (maximal repetition)maximal repetition

Mathematics Subject Classification ID

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