Searching for gapped palindromes

DOI10.1016/J.TCS.2009.09.013zbMath1187.68367OpenAlexW2117575253WikidataQ58064504 ScholiaQ58064504MaRDI QIDQ1038475

Gregory Kucherov, Roman M. Kolpakov

Publication date: 18 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.013

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (22)

Palindromic subsequence automata and longest common palindromic subsequence ⋮ Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes ⋮ Palindromic decompositions with gaps and errors ⋮ Longest Gapped Repeats and Palindromes ⋮ Palindrome pattern matching ⋮ Longest $$\alpha $$-Gapped Repeat and Palindrome ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Smallest and Largest Block Palindrome Factorizations ⋮ Efficient retrieval of approximate palindromes in a run-length encoded string ⋮ 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 ⋮ Computing Longest Single-arm-gapped Palindromes in a String ⋮ Palindromic Decompositions with Gaps and Errors ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Palindrome Pattern Matching ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Detecting regularities on grammar-compressed strings ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Finding Gapped Palindromes Online ⋮ Faster queries for longest substring palindrome after block edit ⋮ Small-space LCE data structure with constant-time queries ⋮ Local symmetry dynamics in one-dimensional aperiodic lattices: a numerical study ⋮ Longest substring palindrome after edit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Palindrome recognition in real time by a multitape Turing machine
• Palindromes in the Fibonacci word
• Palindrome recognition using a multidimensional tape.
• Palindrome complexity.
• Finding approximate palindromes in strings
• Finding all periods and initial palindromes of a string in parallel
• Palindromes and Sturmian words
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Linear work suffix array construction
• On the design of some systolic algorithms
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• Developments in Language Theory
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines

This page was built for publication: Searching for gapped palindromes