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

DOI10.1007/s00224-017-9794-5zbMath1386.68120OpenAlexW2746968256MaRDI QIDQ1702853

Shunsuke Inenaga, Florin Manea, Paweł Gawrychowski, Tomohiro I., Dominik Köppl

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

zbMATH Keywords

combinatorics on wordscounting algorithms

Mathematics Subject Classification ID

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

Related Items (10)

Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes ⋮ Minimal unique palindromic substrings after single-character substitution ⋮ Maximal closed substrings ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Some results on the number of periodic factors in words ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Universal reconstruction of a string ⋮ Efficient representation and counting of antipower factors in words ⋮ Faster queries for longest substring palindrome after block edit ⋮ Longest substring palindrome after edit

Cites Work

• Unnamed Item
• Computing maximal-exponent factors in an overlap-free word
• Searching for gapped palindromes
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Computing longest previous non-overlapping factors
• Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
• Making deterministic signatures quickly
• Longest Gapped Repeats and Palindromes
• Longest $$\alpha $$-Gapped Repeat and Palindrome
• A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
• Finding Pseudo-Repetitions
• Testing Generalised Freeness of Words
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Linear work suffix array construction
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• 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

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