Efficient algorithms to compute compressed longest common substrings and compressed palindromes

DOI10.1016/j.tcs.2008.12.016zbMath1162.68038OpenAlexW2060047347MaRDI QIDQ1006070

Kazuo Hashimoto, Akira Ishino, Shunsuke Inenaga, Wataru Matsubara, Ayumi Shinohara, Tomoyuki Nakamura

Publication date: 17 March 2009

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

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

zbMATH Keywords

text compressionpalindromeslongest common substringstraight line programstring processing algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (22)

Palindromic subsequence automata and longest common palindromic subsequence ⋮ Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ FINDING CHARACTERISTIC SUBSTRINGS FROM COMPRESSED TEXTS ⋮ Minimal unique palindromic substrings after single-character substitution ⋮ Linear-time text compression by longest-first substitution ⋮ Compact q-gram profiling of compressed strings ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ A subquadratic algorithm for minimum palindromic factorization ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ Efficient retrieval of approximate palindromes in a run-length encoded string ⋮ Time-space trade-offs for longest common extensions ⋮ An efficient algorithm to test square-freeness of strings compressed by straight-line programs ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Finding maximal 2-dimensional palindromes ⋮ Functional programs as compressed data ⋮ Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings ⋮ Detecting regularities on grammar-compressed strings ⋮ FINDING ALL APPROXIMATE GAPPED PALINDROMES ⋮ Faster queries for longest substring palindrome after block edit ⋮ A Space-Optimal Grammar Compression. ⋮ Longest substring palindrome after edit

Cites Work

• Unnamed Item
• Parallel detection of all palindromes in a string
• Processing Compressed Texts: A Tractability Border
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Universal lossless compression via multilevel pattern matching
• Efficient algorithms for Lempel-Ziv encoding
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Automata, Languages and Programming
• Developments in Language Theory
• Querying and Embedding Compressed Texts

This page was built for publication: Efficient algorithms to compute compressed longest common substrings and compressed palindromes