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.