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

DOI10.1016/J.TCS.2012.01.023MaRDI QIDQ428850zbMATH OpenOpenAlexFDO

Authors Kuan-Yu Chen, Ping-Hui Hsu, 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 distancepalindromerun-length encoding

Mathematics Subject Classification ID

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

Recommendations

• Identifying approximate palindromes in run-length encoded strings
• scientific article; zbMATH DE number 1786446
• Finding approximate palindromes in strings
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Approximate matching of run-length compressed strings

Cites work

• scientific article; zbMATH DE number 3478847 (Why is no real title available?)
• scientific article; zbMATH DE number 1045405 (Why is no real title available?)
• scientific article; zbMATH DE number 742992 (Why is no real title available?)
• A fast algorithm for finding the positions of all squares in a run-length encoded string
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Algorithms on Strings, Trees and Sequences
• Computational geometry. Algorithms and applications.
• Efficient algorithms for Lempel-Ziv encoding
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• FINDING ALL APPROXIMATE GAPPED PALINDROMES
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Pattern Matching in Strings
• Finding all periods and initial palindromes of a string in parallel
• Finding approximate palindromes in strings
• Hardness of comparing two run-length encoded strings
• On the design of some systolic algorithms
• On the sorting-complexity of suffix tree construction
• Palindrome recognition in real time by a multitape Turing machine
• Searching for gapped palindromes
• Sequence comparison. Theory and methods
• String matching in Lempel-Ziv compressed strings

Cited in

(11)

• Identifying approximate palindromes in run-length encoded strings
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• 2-dimensional palindromes with \(k\) mismatches
• Efficient Computation of Palindromes in Sequences with Uncertainties*
• Streaming for aibohphobes: longest palindrome with mismatches
• Palindromic rich words and run-length encodings
• scientific article; zbMATH DE number 6691399 (Why is no real title available?)
• Finding maximal 2-dimensional palindromes
• Almost linear time computation of maximal repetitions in run length encoded strings
• Approximate On-line Palindrome Recognition, and Applications

This page was built for publication: Efficient retrieval of approximate palindromes in a run-length encoded string

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428850)