A linear space algorithm for computing maximal common subsequences

D. S. Hirschberg · Communications of the ACM · 1975

The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadratic time and in linear space.

Cited by 1,093 works. doi:10.1145/360825.360861 Open-access PDF

Authors

References