LCS(Longest Common Subsequence) Suffix question. I need to modify the theorem fr

Question

LCS(Longest Common Subsequence) Suffix question.

I need to modify the theorem from prefix to suffix.

Original:

Xi = prefix ? x1, ..., xi ?

Yi = prefix ? y1, ..., yi ?

Theorem: 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 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.

Suffix version:

Xi = suffix ?xi, ... , xm?

Yj = suffix ?yj, ... , yn?

Problem #1: Let Z = ? z1 , ..., zk ? be any LCS of X = ? x1 , ..., xm ? and Y = ? y1 , ..., yn ?

If xm = yn, then zk = xm = yn, and Zk?1 is an LCS of Xm-1 and Yn-1.

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.

Problem #2: Redefine the Recursive formulation ?accordingly (fill in the “…”): Define c[i, j] = length of LCS of Xi and Yj . We want to find

not sure where to change.. changing - to + would be enough? or wrong?

I think it is not so difficult, but need some help..

Explanation / Answer

Recursive formulation:

Base case: C[0,j] = 0 and C[i,0] = 0 for all i, j
Recursive step, to compute C[i,j] where i,j > 0:
   If xi = yj , C[i,j] = C[i-1,j-1] + 1
    If xi yj , C[i,j] = max(C[i,j-1], C[i-1,j])
  
Initialize C[i,0] = C[0,j] = 0 for i in [0..m], j in [0..n]
Initialize C[i,j] = NIL for i in [1..m], j in [1..n]

LCS(i, j) // i, j are indices
if C[i, j] = NIL // could use other sentinel value
       then if xi = yj
               then C[i, j] <----- LCS(i-1, j-1) + 1 // one less of both X,Y
            else C[i, j] <---- max(LCS (i, j-1), LCS (i-1, j))
return C[i, j]

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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