Longest common subsequence: Difference between revisions
Content deleted Content added
Line 338:
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.
A binary search optimization due to Hunt and Szymanski can be applied in this case, which results in expected performance of O(s log s) where s = m+n. In the worst case, however, performance degrades to O(m*n log s) time as the number of matches [and the space required to represent them] grows to O(m*n).
'''References'''
| |||