Searching for gapped palindromes

DOI10.1016/j.tcs.2009.09.013zbMath1187.68367WikidataQ58064504 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

68R15: Combinatorics on words

Related Items

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

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