×

Matching for run-length encoded strings. (English) Zbl 0921.68041

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.

MSC:

68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
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.