Optimal bounds for computing \({\alpha}\)-gapped repeats

DOI10.1016/j.ic.2019.104434zbMath1434.68382OpenAlexW4205527277MaRDI QIDQ2272989

Gregory Kucherov, Maxime Crochemore, Roman M. Kolpakov

Publication date: 17 September 2019

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://hal-auf.archives-ouvertes.fr/hal-01577120/file/main-lncs.pdf

zbMATH Keywords

time complexitycombinatorial algorithmscombinatorics on wordsrepeatsalgorithms on stringsgapped repeatssubrepetitions

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (2)

Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Computing the maximum exponent in a stream

Cites Work

• Unnamed Item
• Unnamed Item
• On the maximal sum of exponents of runs in a string
• String processing and information retrieval. 22nd international symposium, SPIRE 2015, London, UK, September 1--4, 2015. Proceedings
• New simple efficient algorithms computing powers and runs in strings
• A \(d\)-step approach to the maximum number of distinct squares and runs in strings
• On primary and secondary repetitions in words
• Computing runs on a general alphabet
• Maximal repetitions in strings
• How many runs can a string contain?
• On maximal repetitions of arbitrary exponent
• Searching for gapped palindromes
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• On the number of gapped repeats with arbitrary gap
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Time-space-optimal string matching
• Squares, cubes, and time-space efficient string searching
• The number of runs in a string
• Longest Gapped Repeats and Palindromes
• Longest $$\alpha $$-Gapped Repeat and Palindrome
• A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
• An O(n log n) algorithm for finding all repetitions 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
• A new characterization of maximal repetitions by Lyndon trees
• Faster Longest Common Extension Queries in Strings over General Alphabets
• Algorithms on Strings
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound

This page was built for publication: Optimal bounds for computing \({\alpha}\)-gapped repeats