Searching of gapped repeats and subrepetitions in a word

DOI10.1016/j.jda.2017.10.004zbMath1380.68324OpenAlexW3021923872MaRDI QIDQ1679608

Nickolay Khrapov, Mikhail L. Podolsky, Roman M. Kolpakov, Mikhail A. Posypkin

Publication date: 9 November 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2017.10.004

zbMATH Keywords

time complexitycombinatorial algorithmsrepetitionscombinatorics on words

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (6)

Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes ⋮ Factorizing strings into repetitions ⋮ Maximal closed substrings ⋮ On the number of gapped repeats with arbitrary gap ⋮ Some results on the number of periodic factors in words ⋮ Efficient representation and counting of antipower 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
• On maximal repetitions of arbitrary exponent
• An optimal algorithm for computing the repetitions 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
• Towards a Solution to the “Runs” Conjecture
• Design and implementation of an efficient priority queue
• 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
• Algorithms on Strings

This page was built for publication: Searching of gapped repeats and subrepetitions in a word