Optimal bounds for computing -gapped repeats
From MaRDI portal
Publication:2272989
DOI10.1016/J.IC.2019.104434zbMATH Open1434.68382OpenAlexW4205527277MaRDI QIDQ2272989FDOQ2272989
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
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 \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets
- Searching of Gapped Repeats and Subrepetitions in a Word
combinatorics on wordstime complexitycombinatorial algorithmsalgorithms on stringsrepeatsgapped repeatssubrepetitions
Cites Work
- Algorithms on Strings, Trees and Sequences
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- Title not available (Why is that?)
- Time-space-optimal string matching
- Title not available (Why is that?)
- Computing runs on a general alphabet
- Squares, cubes, and time-space efficient string searching
- An O(n log n) algorithm for finding all repetitions in a string
- Algorithms on Strings
- A \(d\)-step approach to the maximum number of distinct squares and runs in strings
- 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
- Searching for gapped palindromes
- On the maximal sum of exponents of runs in a string
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
- Maximal repetitions in strings
- How many runs can a string contain?
- Towards a Solution to the “Runs” Conjecture
- The number of runs in a string
- A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
- A new characterization of maximal repetitions by Lyndon trees
- On maximal repetitions of arbitrary exponent
- Efficiently finding all maximal \(\alpha\)-gapped repeats
- Searching of Gapped Repeats and Subrepetitions in a Word
- On primary and secondary repetitions in words
- On the number of gapped repeats with arbitrary gap
- Faster longest common extension queries in strings over general alphabets
- Longest \(\alpha \)-gapped repeat and palindrome
- Near-optimal computation of runs over general alphabet via non-crossing LCE queries
Cited In (9)
- A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
- Computing the maximum exponent in a stream
- Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
- 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
- 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 Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences
- Efficiently finding all maximal \(\alpha\)-gapped repeats
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)
