Longest Common Subsequence - Suffix Approach (Algorithms) Information Regarding

Question

Longest Common Subsequence - Suffix Approach (Algorithms)

Information Regarding Theorem 15.1 prefix version below:

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

If xm = yn, then zk = xm = yn, and Zk?1 is an LCS of Xm?1 and Yn?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 xm ? yn, then zk ? xm ? Z is an LCS of Xm?1 and Y.

If xm ? yn, then zk ? yn ? Z is an LCS of X and Yn?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.)

Explanation / Answer

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.)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.