LCS algorithm that consumes Liner Space

LCS problem is a classical problem of Dynamic Programming.

This algorithm was proposed by Hirschberg from Princeton University in June, 1975.

There is a simple way to reduce the Space requirement to O(n) by ignoring some previous results. Thus, it can only solve subsequence’s length.

Hirschberg’s algorithm can solve the subsequence itself.