Carleton University
Technical Report TR-04
June 1982
A Practical Longest Common Subsequence Algorithm for Text Collation
Jim des Rivieres
Abstract
Previously published algorithms for finding the longest common subsequence in less than quadratic space are not well suited to the task of finding the differences between long streams of words (text collation). This paper presents a practical incremental algorithm with typical space requirements small enough to allow the handling of large insertions and deletions.