A fast algorithm for computing longest common subsequences

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast algorithm for computing longest common subsequences

Full text

Pdf (391 KB)

Source

Communications of the ACM archive
Volume 20 , Issue 5 (May 1977) table of contents

Pages: 350 - 353

Year of Publication: 1977

ISSN:0001-0782

Authors

James W. Hunt	Stanford Univ., Stanford, CA
Thomas G. Szymanski	Princeton Univ., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 68, Downloads (12 Months): 386, Citation Count: 59

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/359581.359603 What is a DOI?

ABSTRACT

Previously published algorithms for finding the longest common subsequence of two sequences of length n have had a best-case running time of O(n2). An algorithm for this problem is presented which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match. Thus in the worst case the algorithm has a running time of O(n2 log n). However, for those applications where most positions of one sequence match relatively few positions in the other sequence, a running time of O(n log n) can be expected.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Vaclav Chvatal , David A. Klarner , Donald E. Knuth, Selected combinatorial research problems., Stanford University, Stanford, CA, 1972
	2	van Emde Boas, P. Preserving order in a forest in less than logarithmic time. 16th Annual Symp. on Foundations Comptr. Sci., Oct. 1975, pp. 75-84.
	3	Fredman, M.L. On computing the length of longest increasing subsequences. Discrete Mathematics 11, 1 (Jan. 1975), 29-35.
	4	D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
	5	Szymansld, T.G. A special case of the maximal common subsequence problem. TR-170, Dep. Electrical Eng., Princeton U., Princeton, N.J., Jan. 1975.
	6	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
	7	Yao, A.C. and Yao, F.F. On computing the rank function for a set of vectors. UIUCDCS-R-75-699, Dep. Comptr. Sci., U. of Illinois at Urbana-Champaign, Urbana, Ill., Feb. 1975.

CITED BY 59

	Brenda S. Baker, A theory of parameterized pattern matching: algorithms and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.71-80, May 16-18, 1993, San Diego, California, United States
	Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France
	R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984
	James Gosling, A redisplay algorithm, ACM SIGPLAN Notices, v.16 n.6, p.123-129, June 1981
	W. J. Hsu, New algorithms for comparing symbol sequences, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.381-389, December 1987, Dallas, Texas, United States
	T. Mens, A State-of-the-Art Survey on Software Merging, IEEE Transactions on Software Engineering, v.28 n.5, p.449-462, May 2002
	Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984
	Bernhard Westfechtel, Structure-oriented merging of revisions of software documents, Proceedings of the 3rd international workshop on Software configuration management, p.68-79, June 12-14, 1991, Trondheim, Norway
	Robert Nix, Editing by example, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.186-195, January 15-18, 1984, Salt Lake City, Utah, United States
	H. Bunke , J. Csirik, Edit distance of run-length coded strings, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.137-143, April 1992, Kansas City, Missouri, United States
	David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming I: linear cost functions, Journal of the ACM (JACM), v.39 n.3, p.519-545, July 1992
	Brenda S. Baker, Parameterized diff, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.854-855, January 17-19, 1999, Baltimore, Maryland, United States
	Christoph Reichenberger, Delta storage for arbitrary non-text files, Proceedings of the 3rd international workshop on Software configuration management, p.144-152, June 12-14, 1991, Trondheim, Norway
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	M. -W. Du , S. C. Chang, An Approach to Designing Very Fast Approximate String Matching Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.620-633, August 1994
	Robert P. Nix, Editing by example, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.600-621, Oct. 1985
	Campbell B. Fraser , Robert W. Irving, Approximation algorithms for the shortest common supersequence, Nordic Journal of Computing, v.2 n.3, p.303-325, Fall 1995
	David Gitchell , Nicholas Tran, Sim: a utility for detecting similarity in computer programs, ACM SIGCSE Bulletin, v.31 n.1, p.266-270, March 1999
	Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977
	James J. Hunt , Kiem-Phong Vo , Walter F. Tichy, Delta algorithms: an empirical analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.192-214, April 1998
	Claus Rick, A new flexible algorithm for the longest common subsequence problem, Nordic Journal of Computing, v.2 n.4, p.444-461, Winter 1995
	I. Dan Melamed, Bitext maps and alignment via pattern recognition, Computational Linguistics, v.25 n.1, p.107-130, March 1999
	David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.513-522, January 22-24, 1990, San Francisco, California, United States
	Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979
	Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991
	C. E. R. Alves , E. N. Cáceres , F. Dehne, Parallel dynamic programming for solving the string editing problem on a CGM/BSP, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Maxime Crochemore , Costas S. Ilipoulos , Yoan J. Pinzon, Speeding-up Hirschberg and Hunt-Szymanski LCS algorithms, Fundamenta Informaticae, v.56 n.1,2, p.89-103, July 2003
	Gad M. Landau , Baruch Schieber , Michal Ziv-Ukelson, Sparse LCS common substring alignment, Information Processing Letters, v.88 n.6, p.259-270, 31 December 2003
	James R. Cordy , Thomas R. Dean , Nikita Synytskyy, Practical language-independent detection of near-miss clones, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.1-12, October 04-07, 2004, Markham, Ontario, Canada
	Eric A. Breimer , Mark K. Goldberg , Darren T. Lim, A learning algorithm for the longest common subsequence problem, Journal of Experimental Algorithmics (JEA), 8, 2003
	B. J. Oommen , K. Zhang , W. Lee, Numerical Similarity and Dissimilarity Measures Between Two Trees, IEEE Transactions on Computers, v.45 n.12, p.1426-1434, December 1996
	Michael H. Albert , Alexander Golynski , Angèle M. Hamel , Alejandro López-Ortiz , S. Srinivasa Rao , Mohammad Ali Safari, Longest increasing subsequences in sliding windows, Theoretical Computer Science, v.321 n.2-3, p.405-414, 16 August 2004
	J. Y. Guo , F. K. Hwang, An almost-linear time and linear space algorithm for the longest common subsequence problem, Information Processing Letters, v.94 n.3, p.131-135, 16 May 2005
	Valerio Freschi , Alessandro Bogliolo, Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism, Information Processing Letters, v.90 n.4, p.167-173, 31 May 2004
	S. Kuo , G. R. Cross, An improved algorithm to find the length of the longest common subsequence of two strings, ACM SIGIR Forum, v.23 n.3-4, p.89-99, Spring 1989
	Jonathan I. Maletic , Michael L. Collard , Bonita Simoes, An XML based approach to support the evolution of model-to-model traceability links, Proceedings of the 3rd international workshop on Traceability in emerging forms of software engineering, November 08-08, 2005, Long Beach, California
	Veli Mäkinen , Gonzalo Navarro , Esko Ukkonen, Transposition invariant string matching, Journal of Algorithms, v.56 n.2, p.124-153, August 2005
	Miryung Kim , David Notkin, Program element matching for multi-version program analyses, Proceedings of the 2006 international workshop on Mining software repositories, May 22-23, 2006, Shanghai, China
	Hui Kong , Tan Yan , Martin D. F. Wong , Muhammet Mustafa Ozdal, Optimal bus sequencing for escape routing in dense PCBs, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Sebastian Deorowicz, Speeding up transposition-invariant string matching, Information Processing Letters, v.100 n.1, p.14-20, 16 October 2006
	Robert H. Warren , Frank Wm. Tompa, Multi-column substring matching for database schema translation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Michel Neuhaus , Horst Bunke, Edit distance-based kernel functions for structural pattern classification, Pattern Recognition, v.39 n.10, p.1852-1863, October, 2006
	Martin P. Robillard , Gail C. Murphy, Representing concerns in source code, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.1, p.3-es, February 2007
	Costas S. Iliopoulos , M. Sohel Rahman, New efficient algorithms for the LCS and constrained LCS problems, Information Processing Letters, v.106 n.1, p.13-18, March, 2008
	Michael D. Morse , Jignesh M. Patel, An efficient and accurate method for evaluating time series similarity, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Miryung Kim , David Notkin , Dan Grossman, Automatic Inference of Structural Changes for Matching across Program Versions, Proceedings of the 29th International Conference on Software Engineering, p.333-343, May 20-26, 2007
	Danny Dig , Kashif Manzoor , Ralph Johnson , Tien N. Nguyen, Refactoring-Aware Configuration Management for Object-Oriented Programs, Proceedings of the 29th International Conference on Software Engineering, p.427-436, May 20-26, 2007
	Wilburt Labio , Hector Garcia-Molina, Efficient Snapshot Differential Algorithms for Data Warehousing, Proceedings of the 22th International Conference on Very Large Data Bases, p.63-74, September 03-06, 1996
	R. D. Dowsing , S. Long , M. R. Sleep, Assessing word processing skills by computer, Information Services and Use, v.18 n.1,2, p.15-24, January 1998
	Gad M. Landau , Eugene Myers , Michal Ziv-Ukelson, Two algorithms for LCS Consecutive Suffix Alignment, Journal of Computer and System Sciences, v.73 n.7, p.1095-1117, November, 2007
	C. E. R. Alves , E. N. Cáceres , S. W. Song, An all-substrings common subsequence algorithm, Discrete Applied Mathematics, v.156 n.7, p.1025-1035, April, 2008
	J. J. Liu , Y. L. Wang , R. C. T. Lee, Finding a longest common subsequence between a run-length-encoded string and an uncompressed string, Journal of Complexity, v.24 n.2, p.173-184, April, 2008
	Xiaoming Sun , David P. Woodruff, The communication and streaming complexity of computing the longest common and increasing subsequences, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.336-345, January 07-09, 2007, New Orleans, Louisiana
	Hsing-Yen Ann , Chang-Biau Yang , Chiou-Ting Tseng , Chiou-Yi Hor, A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings, Information Processing Letters, v.108 n.6, p.360-364, November, 2008
	Costas S. Iliopoulos , M. Sohel Rahman, Algorithms for computing variants of the longest common subsequence problem, Theoretical Computer Science, v.395 n.2-3, p.255-267, May, 2008
	Beat Fluri , Michael Wuersch , Martin PInzger , Harald Gall, Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction, IEEE Transactions on Software Engineering, v.33 n.11, p.725-743, November 2007
	Kuo-Tsung Tseng , Chang-Biau Yang , Kuo-Si Huang , Yung-Hsing Peng, Near-Optimal Block Alignments, IEICE - Transactions on Information and Systems, v.E91-D n.3, p.789-795, March 2008
	Yoshifumi Sakai, Note: Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence, Theoretical Computer Science, v.410 n.27-29, p.2759-2766, June, 2009
	Hui Wang , Chang Liu, Neighbourhood Counting Metric for Sequences, Proceeding of the 2006 conference on Advances in Intelligent IT: Active Media Technology 2006, p.243-248, May 19, 2006

INDEX TERMS

Keywords:
efficient algorithms, longest common subsequence

Collaborative Colleagues:

James W. Hunt: colleagues

Thomas G. Szymanski: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player