Longest Common Subsequence Suffix Approach Algorithms Infor

Longest Common Subsequence - Suffix Approach (Algorithms)

Information Regarding Theorem 15.1 prefix version below:

Theorem 15.1 : Let Z = ? z₁, ..., z_k ? be any LCS of X = ? x₁, ..., x_m ? and Y = ? y₁, ..., y_n ?. Then

If x_m = y_n, then z_k = x_m = y_n, and Z_k?1 is an LCS of X_m?1 and Y_n?1.
(If the last characters of X and Y match, then these last characters are also the last character of the LCS Z, so we can discard the last character of all three and continue recursively on the prefix.)

If x_m ? y_n, then z_k ? x_m ? Z is an LCS of X_m?1 and Y.

If x_m ? y_n, then z_k ? y_n ? Z is an LCS of X and Y_n?1.
(If the last characters of X and Y don\'t match each other, then the prefix Z must be in the substrings not involving these characters, and furthermore we can use the last character of Z to determine which one it lies in.)

Solution

The answer in the underlined

Let Z = z1, ..., zk be any LCS of X = x1, ..., xm and Y = y1, ..., yn . Then

1. If x1= y1, then z1 = x1 = y1, and Z2 is an LCS of X2 and Y2
2. (If the first characters of X and Y match, then these first characters are also the first character of the LCS Z, so we can discard the first character of all three and continue recursively on the suffics.)

3. If x1 y1, then z1 x1 Z is an LCS of X2 and Y.

4. If x1 y1, then z1 y1 Z is an LCS of X and Y2.
5. (If the first characters of X and Y don\'t match each other, then the suffics Z must be in the substrings not involving these characters, and furthermore we can use the first character of Z to determine which one it lies in.)