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

DOI10.1016/J.TCS.2012.01.023zbMATH Open1242.68383OpenAlexW1967161177MaRDI QIDQ428850FDOQ428850

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

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

zbMATH Keywords

Hamming distancepalindromerun-length encoding

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Palindromic rich words and run-length encodings
• Finding maximal 2-dimensional palindromes
• 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
• Identifying approximate palindromes in run-length encoded strings
• Almost linear time computation of maximal repetitions in run length encoded strings
• Efficient Computation of Palindromes in Sequences with Uncertainties*
• Title not available (Why is that?)
• Approximate On-line Palindrome Recognition, and Applications
• EERTREE: an efficient data structure for processing palindromes in strings
• 2-dimensional palindromes with \(k\) mismatches

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)