A Linear Space Algorithm for Computing Maximal Common Subsequences

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.

CACM June, 1975

Hirschberg, D. S.

subsequence, longest common subsequence, string correction, editing

3.63 3.73 3.79 4.22 5.25

CA750608 JB January 9, 1978  12:56 PM

2745	5	2745
2745	5	2745
2745	5	2745
2963	5	2745
3114	5	2745
1502	6	2745
2499	6	2745
2745	6	2745
2745	6	2745