Efficient retrieval of approximate palindromes in a run-length encoded string

DOI10.1016/j.tcs.2012.01.023zbMath1242.68383OpenAlexW1967161177MaRDI QIDQ428850

Ping-Hui Hsu, Kuan-Yu Chen, Kun-Mao Chao

Publication date: 25 June 2012

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

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

zbMATH Keywords

Hamming distancerun-length encodingpalindrome

Mathematics Subject Classification ID

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

Related Items

2-dimensional palindromes with \(k\) mismatches ⋮ Finding maximal 2-dimensional palindromes ⋮ Almost linear time computation of maximal repetitions in run length encoded strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast algorithm for finding the positions of all squares in a run-length encoded string
• Sequence comparison. Theory and methods
• Hardness of comparing two run-length encoded strings
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Searching for gapped palindromes
• Palindrome recognition in real time by a multitape Turing machine
• String matching in Lempel-Ziv compressed strings
• Finding approximate palindromes in strings
• Finding all periods and initial palindromes of a string in parallel
• FINDING ALL APPROXIMATE GAPPED PALINDROMES
• Fast Algorithms for Finding Nearest Common Ancestors
• On the design of some systolic algorithms
• A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• Efficient algorithms for Lempel-Ziv encoding
• On the sorting-complexity of suffix tree construction