Algorithms for the Longest Common Subsequence Problem
Daniel S. Hirschberg · Journal of the ACM · 1977
AaS~ACT Two algorithms are presented that solve the longest common subsequence problem The first algorithm is applicable in the general case and requires O(pn + n log n) time where p is the length of the longest common subsequence The second algorithm requires time bounded by O(p(m + 1 -p)log n) In the common speoal case where p is close to m, this algorithm takes much less time than n ~
Cited by 750 works. doi:10.1145/322033.322044 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- A general method applicable to the search for similarities in the amino acid sequence of two proteins
- The Art of Computer Programming: Volume 3: Sorting and Searching
- The String-to-String Correction Problem
- Matching Sequences under Deletion/Insertion Constraints
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- A linear space algorithm for computing maximal common subsequences
- Selected combinatorial research problems.
- A fast algorithm for computing longest common subsequences
- An Extension of the String-to-String Correction Problem