Apostolico, Alberto; Landau, Gad M.; Skiena, Steven Matching for run-length encoded strings. (English) Zbl 0921.68041 J. Complexity 15, No. 1, 4-16 (1999). Summary: Measuring the similarity between two strings, through such standard measures as Hamming distance, edit distance, and longest common subsequence, is one of the fundamental problems in pattern matching. We consider the problem of finding the longest common subsequence of two strings. A well-known dynamic programming algorithm computes the longest common subsequence of strings \(X\) and \(Y\) in \(O(| X|\cdot| Y|)\) time. In this paper, we develop significantly faster algorithms for a special class of strings which emerge frequently in pattern matching problems. Cited in 21 Documents MSC: 68W10 Parallel algorithms in computer science Keywords:pattern matching PDFBibTeX XMLCite \textit{A. Apostolico} et al., J. Complexity 15, No. 1, 4--16 (1999; Zbl 0921.68041) Full Text: DOI Link References: [1] Aho, A. V.; Hirschberg, D. S.; Ullman, J. D., Bounds on the complexity of the longest common subsequence problem, J. Assoc. Comput. Mach., 23, 1-12 (1976) · Zbl 0316.68027 [2] Apostolico, A., String editing and longest common subsequences, Handbook of Formal Languages (1996), Springer-Verlag: Springer-Verlag New York/Berlin, p. 361-398 [3] Bunke, H.; Csirik, J., An improved algorithm for computing the edit distance of run-length coded strings, Inform. Process. Lett., 54, 93-96 (1995) · Zbl 1004.68598 [4] Hirschberg, D. S., An information theoretic lower bound for the longest common subsequence problem, Inform. Process. Lett., 7, 40-41 (1978) · Zbl 0365.94025 [5] Hirschberg, D. S., A linear space algorithm for computing maximal common subsequences, Comm. CACM, 18, 341-343 (1975) · Zbl 0301.68042 [6] Hirschberg, D. S.; Larmore, L. L., The set-set LCS problem, Algorithmica, 4, 503-510 (1989) · Zbl 0684.68080 [7] Masek, W. J.; Paterson, M., A faster algorithm computing string edit distances, J. Comput. System Sci., 20, 18-31 (1989) · Zbl 0436.68044 [8] Mitchell, J., Technical Report (1997) [9] G. Sazaklis, E. Arkin, J. Mitchell, S. Skiena, Geometric decision trees for optical character recognition, Proc. 13th ACM Symposium on Computational Geometry, 1997; G. Sazaklis, E. Arkin, J. Mitchell, S. Skiena, Geometric decision trees for optical character recognition, Proc. 13th ACM Symposium on Computational Geometry, 1997 [10] Wang, B.; Chen, G.; Park, K., On the set LCS and set-set LCS problems, J. Algorithms, 14, 466-477 (1993) · Zbl 0797.68067 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.