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
DOI10.1007/S00224-017-9794-5zbMATH Open1386.68120OpenAlexW2746968256MaRDI QIDQ1702853FDOQ1702853
Authors: Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea 
Publication date: 1 March 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9794-5
Recommendations
- Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes
- A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
- Optimal bounds for computing \({\alpha}\)-gapped repeats
- Optimal bounds for computing \(\alpha\)-gapped repeats
- Efficiently finding all maximal \(\alpha\)-gapped repeats
- Almost linear time computation of maximal repetitions in run length encoded strings
- Longest \(\alpha \)-gapped repeat and palindrome
- Alphabet-independent algorithms for finding context-sensitive repeats in linear time
Cites Work
- Algorithms on Strings, Trees and Sequences
- Linear work suffix array construction
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Title not available (Why is that?)
- The ``runs theorem
- Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
- Searching for gapped palindromes
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- Computing longest previous non-overlapping factors
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
- A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
- Computing maximal-exponent factors in an overlap-free word
- Finding pseudo-repetitions
- Testing generalised freeness of words
- Efficiently finding all maximal \(\alpha\)-gapped repeats
- Searching of Gapped Repeats and Subrepetitions in a Word
- Optimal bounds for computing \(\alpha\)-gapped repeats
- Making deterministic signatures quickly
- Longest \(\alpha \)-gapped repeat and palindrome
Cited In (16)
- Longest substring palindrome after edit
- Optimal bounds for computing \({\alpha}\)-gapped repeats
- A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string
- Universal reconstruction of a string
- Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes
- Searching of gapped repeats and subrepetitions in a word
- Some results on the number of periodic factors in words
- Optimal bounds for computing \(\alpha\)-gapped repeats
- Maximal closed substrings
- Minimal unique palindromic substrings after single-character substitution
- Computing longest palindromic substring after single-character or block-wise edits
- Internal pattern matching queries in a text and applications
- Efficiently finding all maximal \(\alpha\)-gapped repeats
- Faster queries for longest substring palindrome after block edit
- Efficient computation of longest single-arm-gapped palindromes in a string
- Longest \(\alpha \)-gapped repeat and palindrome
This page was built for publication: 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702853)
