- Distinguish between the two different UNIX program
- Construct lists of the equivalence classes of elements in the second ﬁle. These lists occupy O(n) space. They can be made by sorting the lines of the second ﬁle
- Associate the appropriate equivalence class with each element of the ﬁrst ﬁle. This association can be stored in O(m) space. In effect now we hav e a list of the dots for each vertical
- searching phase in
(**O***n**m*log*n*) time complexity - searching phase in
(**O***m**n*) space complexity

The program diff reports differences between two files, expressed as a minimal list of line changes to bring either file into agreement with the other. Diff has been engineered to make efficient use of time and space on typical inputs that arise in vetting version-to-version changes in computer-maintained or computer-generated documents. Time and space usage are observed to vary about as the sum of the file lengths on real data, although they are known to vary as the product of the file lengths in the worst case. The central algorithm of diff solves the longest common subsequence problem’ to find the lines that do not change between files. Practical efficiency is gained by attending only to certain critical ‘candidate’ matches between the files, the breaking of which would shorten the longest subsequence common to some pair of initial segments of the two files. Various techniques of hashing, presorting into equivalence classes, merging by binary search, and dynamic storage allocation are used to obtain good performance.

int Diff_Alg(char *stringA, char *stringB, int m, int n) { int i, j, rowMax = 0; kCandidateList *kList; kList = (kCandidateList*) calloc(min(m, n) + 1, sizeof(kCandidateList)); // Find Match for (i = 1; i <= m; i++){ for (j = n; j >= 1; j--){ if (stringA[i] == stringB[j]){ rowMax = HMAlg(kList, j, i, rowMax); } } } return rowMax; }

J. W. Hunt and M. D. McIlroy, "An Algorithm for Differential File Comparison," Computing Science Technical Report 41, Bell Laboratories (1975).