When there is a recursive algorithm based on the subproblems but the total number of subproblems is not too great, it is possible to cache all solutions in a table. In the case of a longest common subsequence detection, running through all the subsequences would take exponential time. Instead we can define a recursion based on the following :
Let c[i, j] be the length of the longest common subsequence of the prefix of X[1..i] and Y[1..j]. Recursion:
c[i, j] = { 0 if i = 0 or j = 0
= { c[i-1, j-1] + 1 if i,j > 0 and xi = yj
= { max( c[i,j-1], c[i-1,j] ) otherwise
This way we utilize the solutions we computed. We compute the table c[i,j] bottom-up and also store the value b[i,j] that captures whether c[i,j-1], c[i-1,j] or c[i-1,j-1] + 1is optimum. We therefore find the longest common subsequence by walking backwards on the path from the last cell of b[i,j] to the first.
Let c[i, j] be the length of the longest common subsequence of the prefix of X[1..i] and Y[1..j]. Recursion:
c[i, j] = { 0 if i = 0 or j = 0
= { c[i-1, j-1] + 1 if i,j > 0 and xi = yj
= { max( c[i,j-1], c[i-1,j] ) otherwise
This way we utilize the solutions we computed. We compute the table c[i,j] bottom-up and also store the value b[i,j] that captures whether c[i,j-1], c[i-1,j] or c[i-1,j-1] + 1is optimum. We therefore find the longest common subsequence by walking backwards on the path from the last cell of b[i,j] to the first.
No comments:
Post a Comment