On the number of gapped repeats with arbitrary gap

DOI10.1016/j.tcs.2018.03.007zbMath1393.68143arXiv1701.01190OpenAlexW2583336035WikidataQ130120525 ScholiaQ130120525MaRDI QIDQ1708025

Roman M. Kolpakov

Publication date: 4 April 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordsgapped repeatsmaximal number of repeats

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items

Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Some results on the number of periodic factors in words

Cites Work

• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• On the maximal sum of exponents of runs in a string
• On primary and secondary repetitions in words
• An optimal algorithm for computing the repetitions in a word
• Searching of gapped repeats and subrepetitions in a word
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Time-space-optimal string matching
• Squares, cubes, and time-space efficient string searching
• Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
• Longest Gapped Repeats and Palindromes
• Longest $$\alpha $$-Gapped Repeat and Palindrome
• A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
• Towards a Solution to the “Runs” Conjecture
• Algorithms on Strings, Trees and Sequences
• Efficiently Finding All Maximal alpha-gapped Repeats
• Searching of Gapped Repeats and Subrepetitions in a Word
• The “Runs” Theorem