Optimal bounds for computing -gapped repeats

DOI10.1016/J.IC.2019.104434MaRDI QIDQ2272989zbMATH OpenOpenAlexFDO

Authors Maxime Crochemore, Gregory Kucherov, Roman 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

combinatorics on wordstime complexitycombinatorial algorithmsalgorithms on stringsrepeatsgapped repeatssubrepetitions

Mathematics Subject Classification ID

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

Recommendations

• Optimal bounds for computing \(\alpha\)-gapped repeats
• A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
• Efficiently finding all maximal \(\alpha\)-gapped repeats
• Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
• Searching of Gapped Repeats and Subrepetitions in a Word

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3913712 (Why is no real title available?)
• A \(d\)-step approach to the maximum number of distinct squares and runs in strings
• A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
• A new characterization of maximal repetitions by Lyndon trees
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal algorithm for computing the repetitions in a word
• Computing runs on a general alphabet
• Efficiently finding all maximal \(\alpha\)-gapped repeats
• Faster longest common extension queries in strings over general alphabets
• How many runs can a string contain?
• Longest \(\alpha \)-gapped repeat and palindrome
• Maximal repetitions in strings
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• New simple efficient algorithms computing powers and runs in strings
• On maximal repetitions of arbitrary exponent
• On primary and secondary repetitions in words
• On the maximal sum of exponents of runs in a string
• On the number of gapped repeats with arbitrary gap
• Optimal off-line detection of repetitions in a string
• Searching for gapped palindromes
• Searching of Gapped Repeats and Subrepetitions in a Word
• Squares, cubes, and time-space efficient string searching
• String processing and information retrieval. 22nd international symposium, SPIRE 2015, London, UK, September 1--4, 2015. Proceedings
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• The number of runs in a string
• Time-space-optimal string matching
• Towards a Solution to the “Runs” Conjecture

Cited in

(9)

• Efficiently finding all maximal \(\alpha\)-gapped repeats
• Computing the maximum exponent in a stream
• Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes
• Searching of gapped repeats and subrepetitions in a word
• Optimal bounds for computing \(\alpha\)-gapped repeats
• A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences
• 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
• A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272989)