Question

Given two strings $\mathit{x}\mathbf{=}{\mathit{x}}_{\mathbf{1}}{\mathit{x}}_{\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{x}}_{\mathbf{n}}$and $\mathit{y}\mathbf{=}{\mathit{y}}_{\mathbf{1}}{\mathit{y}}_{\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{y}}_{\mathbf{m}}$, we wish to find the length of their longest common subsequence, that is, the largest k for which there are indices ${\mathit{i}}_{\mathbf{1}}\mathbf{<}{\mathit{i}}_{\mathbf{2}}\mathbf{<}\mathbf{·}\mathbf{·}\mathbf{·}\mathbf{<}{\mathit{i}}_{\mathbf{k}}$and ${\mathit{j}}_{\mathbf{1}}\mathbf{<}{\mathit{j}}_{\mathbf{2}}\mathbf{<}\mathbf{·}\mathbf{·}\mathbf{·}\mathbf{<}{\mathit{j}}_{\mathbf{k}}$with ${\mathit{x}}_{\mathbf{i}\mathbf{1}}{\mathit{x}}_{\mathbf{i}\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{x}}_{\mathbf{i}\mathbf{k}}\mathbf{=}{\mathit{y}}_{\mathbf{j}\mathbf{1}}{\mathit{y}}_{\mathbf{j}\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{y}}_{\mathbf{j}\mathbf{k}}$. Show how to do this in time $\mathbf{0}\left(mn\right)$.

Short answer

There are two approaches to doing this problem:

1. Brute Force Method

Here, we will consider all the substring of string$x=x_1{x}_2···x_n$and check if how many of those possible substrings of x can be found in string$y=y_1{y}_2···y_m$.

And also keeping track of maximum length of common substring.

But in this case, the run time is much greater then$0\left(mn\right)$.

2.Dynamic Algorithm Method

Here simultaneously we will find the longest suffix string pattern of both string and store them in a table. This will reduce the function call and hence our runtime will be $0\left(mn\right)$.

Step-by-step solution

Defining Recursive Equation

Let d_i,j be the length of Longest Common Subsequence(LCS) in strings$x=x_1{x}_2···x_n$and$y=y_1{y}_2···y_m$.

Let D be the matrix of $m*n\left[d_{i,j}\right]$. This matrix will act as table to consecutively store the common substring.

Let $Z_k=z_1{z}_2···z_k$be substring common in string ‘x’ and ‘y’, i.e., $Z\left[1...k\right]$is LCS in $X\left[1....i\right]$and$Y\left[1....j\right]$

We have two cases:

• If$x_i=y_i$

That means, z_k=x_i=y_j

And$Z_k$is LCSrole="math" localid="1657268874063" $\left(X\left[1....i-1\right],Y\left[1....j-1\right]\right)$followed by$z_k$.

• If$x_i\ne y_i$

That means,

Either $Z_k=\left(X\left[1....i-1\right],Y\left[1....j\right]\right)$or $Z_k=\left(X\left[1....i\right],Y\left[1....j-1\right]\right)$

So, our recursive equation is:

${\mathit{d}}_{\mathbf{i}\mathbf{,}\mathbf{j}}\mathbf{=}\{\begin{array}{l}0;ifi=0,j=0\\ \begin{array}{c}{d}_{i-1,j-1}+1;if{x}_i=y_j\\ Max\left\{d_{i-1,j},d_{i,j-1}\right\};if{x}_i\ne y_j\end{array}\end{array}$

Algorithm

$$\begin{gathered} m=Length\left(x\right) \\ n=Length\left(y\right) \\ for\left(i=0tom\right) \\ d\left[i,0\right]=0 \\ for\left(j=0ton\right) \\ d\left[0,j\right]=0 \\ for\left(i=1tom\right) \\ for\left(j=1ton\right) \\ if\left(xi=yi\right) \\ d\left[i,j\right]=d\left[i-1,j-1\right]+1 \\ else \\ if\left(d\left[i-1,j\right]\ge d\left[i,j-1\right]\right) \\ d\left[i,j\right]=d\left[i-1,j\right] \\ else \\ d\left[i,j\right]\ge d\left[i,j-1\right] \end{gathered}$$

return$d$

This algorithm will be run in $0\left(mn\right)$time.