Abstract
A new algorithm that is efficient for both short and long longest common subsequences is presented. It also improves on previous algorithms for longest common subsequences of intermediate length. Thus, it is more flexible and can be used for a wider range of applications than others. The algorithm is based on the well-known paradigm of computing dominant matches and was obtained through a kind of dualization. Some experimental results are given, too.
This work is dedicated to my father and to the memory of my mother.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Apostolico, C. Guerra: The Longest Common Subsequence Problem Revisited, Algorithmica, Vol. 2, 1987, 315–336.
F. Y. L. Chin, C. K. Poon: A Fast Algorithm for Computing Longest Common Subsequences of Small Alphabet Size, Journal of Information Processing, Vol. 13, No. 4, 1990, 463–469.
F. Y. L. Chin, C. K. Poon: Performance Analysis of Some Simple Heuristics for Computing Longest Common Subsequences, Algorithmica, Vol. 12, 1994, 293–311.
V. Dančík: Expected Length of Longest Common Subsequences, PhD thesis, University of Warwick, 1994.
D. Eppstein, Z. Galil, R. Giancarlo, G. F. Italiano: Sparse Dynamic Programming I: Linear Cost Functions, Journal of the ACM, Vol. 39, No. 3, 1992, 519–545.
D. S. Hirschberg: Algorithms for the Longest Common Subsequence Problem, Journal ACM, Vol. 24, Oct. 1977, 664–675.
W. J. Hsu, M. W. Du: New Algorithms for the LCS Problem, Journal of Computer and System Sciences 29, 1984, 133–152.
J. W. Hunt, T. G. Szymanski: A Fast Algorithm for Computing Longest Common Subsequences, Comm. ACM, Vol. 20, May 1977, 350–353.
W. J. Masek, M. S. Paterson: A Faster Algorithm Computing String Edit Distances, Journal of Computer and System Sciences 20, 1980, 18–31.
E. W. Myers: An O(N D) Difference Algorithm and Its Variations, Algorithmica, Vol. 1, 1986, 251–266.
N. Nakatsu, Y. Kambayashi, S. Yajima: A Longest Common Subsequence Algorithm Suitable for Similar Text Strings, Acta Informatica 18, 1982, 171–179.
M. Paterson, V. Dancik: Longest Common Subsequences, Proceedings of the 19th Intern. Symp. on Mathematical Foundations of Computer Science, Vol. 841 of LNCS, 1994, 127–142.
C. Rick: New Algorithms for the Longest Common Subsequence Problem, Research Report No. 85123-CS, University of Bonn, 1994.
D. Sankoff, J. B. Kruskal (Ed.): Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley: Reading, MA, 1983.
E. Ukkonen: Algorithms for Approximate String Matching, Information and Control 64, 1985, 100–118.
R. A. Wagner, M. J. Fischer: The String to String Correction Problem, Journal ACM, Vol. 21, 1974, 168–173.
S. Wu, U. Manber, G. Myers, W. Miller: An O(NP) Sequence Comparison Algorithm, Information Processing Letters 35, 1990, 317–323.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rick, C. (1995). A new flexible algorithm for the longest common subsequence problem. In: Galil, Z., Ukkonen, E. (eds) Combinatorial Pattern Matching. CPM 1995. Lecture Notes in Computer Science, vol 937. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60044-2_53
Download citation
DOI: https://doi.org/10.1007/3-540-60044-2_53
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60044-2
Online ISBN: 978-3-540-49412-6
eBook Packages: Springer Book Archive