This is an oldie but a goodie. A string z is a longest common subsequence (or LCS) of strings x and y if the characters of z appear in order in both x and y, and there is no longer string with this property. For example, if x = ghost and y = cohorts, then the longest common subsequences of x and y are hot and hos. An important application of the LCS problem is computing the minimum edit distance of two strings, i.e., the minimum number of insertions, deletions, and replacements necessary to transform one string into another. This is used by spelling checkers to find a word that is "close" to a mispelled word.
It's easy to find the length of an LCS using dynamic programming. Suppose that x has length m and y has length n. We will construct an array L such that L[i, j] is the length of an LCS of x[1..i] and y[1..j], for 0 £ i £ m and 0 £ j £ n. (The notation x[1..i] means the first i characters of x. The first character is at position 1.) We initialize L by setting L[i, 0] and L[0, j] to 0 for all i and j. We then execute the following loop,
for i from 1 to m do
for j from 1 to n do
update L[i,j]
where L[i, j] = L[i - 1, j - 1] + 1 if x[i] = y[j], and otherwise L[i, j] = max(L[i, j - 1], L[i - 1, j]). The final length of an LCS is L[m, n].
Write a program that implements this algorithm. The input will consist of one or more lines, where each line contains two strings separated by a single space. Strings will be nonempty, will not contain spaces, and will be no longer than 80 characters. For each line, output the length of an LCS for the pair of strings.
Input must be read from the file prob44.in, and output must be written to the file prob44.out. All output to the screen will be ignored.
ghost cohorts peanut cocoa algorithm logarithm
Dr. Eric Shade3 1 7