Longest common subsequence: Difference between revisions

Here a "divide and conquer" approach devised by Hirschberg can limit the space required to O(m+n). However, this approach requires O(m*n) time even in the best case.

 

 

In the application of comparing source file revisions, records form a sparse symbol space and generate a linear O(m+n) number of pairs where the input sequences match.