×

zbMATH — the first resource for mathematics

Efficient algorithms to compute compressed longest common substrings and compressed palindromes. (English) Zbl 1162.68038
Summary: This paper studies two problems on compressed strings described in terms of Straight Line Programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in \(O(n^{4} \log n)\) time with \(O(n^{3})\) space, and in \(O(n^{4})\) time with \(O(n^{2})\) space, respectively, where \(n\) is the size of the input SLP-compressed strings.

MSC:
68W05 Nonnumerical algorithms
68R15 Combinatorics on words
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apostolico, A.; Breslauer, D.; Galil, Z., Parallel detection of all palindromes in a string, Theoretical computer science, 141, 163-173, (1995) · Zbl 0873.68039
[2] Gasieniec, L.; Karpinski, M.; Plandowski, W.; Rytter, W., An efficient algorithms for Lempel-Ziv encoding, (), 392-403
[3] Inenaga, S.; Shinohara, A.; Takeda, M., An efficient pattern matching algorithm on a subclass of context free grammars, (), 225-236 · Zbl 1117.68388
[4] Karpinski, M.; Rytter, W.; Shinohara, A., An efficient pattern-matching algorithm for strings with short descriptions, Nordic journal of computing, 4, 172-186, (1997) · Zbl 0874.68087
[5] Kieffer, J.; Yang, E.; Nelson, G.; Cosman, P., Universal lossless compression via multilevel pattern matching, IEEE transactions on information theory, 46, 4, 1227-1245, (2000) · Zbl 1003.94017
[6] Lifshits, Y., Processing compressed texts: A tractability border, (), 228-240 · Zbl 1138.68419
[7] Lifshits, Y.; Lohrey, M., Querying and embedding compressed texts, (), 681-692 · Zbl 1132.68379
[8] Matsubara, W.; Inenaga, S.; Ishino, A.; Shinohara, A.; Nakamura, T.; Hashimoto, K., Computing longest common substring and all palindromes from compressed strings, (), 364-375 · Zbl 1132.68518
[9] Miyazaki, M.; Shinohara, A.; Takeda, M., An improved pattern matching algorithm for strings in terms of straight-line programs, (), 1-11
[10] Nevill-Manning, C.G.; Witten, I.H.; Maulsby, D.L., Compression by induction of hierarchical grammars, (), 244-253
[11] Plandowski, W., Testing equivalence of morphisms on context-free languages, (), 460-470
[12] Rytter, W., Grammar compression, LZ-encodings, and string algorithms with implicit input, (), 15-27 · Zbl 1099.68028
[13] Ziv, J.; Lempel, A., A universal algorithm for sequential data compression, IEEE transactions on information theory, IT, 23, 3, 337-349, (1977) · Zbl 0379.94010
[14] Ziv, J.; Lempel, A., Compression of individual sequences via variable-length coding, IEEE transactions on information theory, 24, 5, 530-536, (1978) · Zbl 0392.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.