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 substring, that is, the largest k for which there are indices i and j with ${\mathit{x}}_{\mathbf{i}}{\mathit{x}}_{\mathbf{i}\mathbf{+}\mathbf{1}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{x}}_{\mathbf{i}\mathbf{+}\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{=}{\mathit{y}}_{\mathbf{j}}{\mathit{y}}_{\mathbf{j}\mathbf{+}\mathbf{1}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{y}}_{\mathbf{j}\mathbf{+}\mathbf{k}\mathbf{-}\mathbf{1}}$. Show how to do this in time$\mathbf{0}\left(mn\right)$

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 role="math" localid="1657260451767" $X\left[1....i\right]$and$Y\left[1....j\right]$

We have two cases:

That means, $z_k=x_i=y_j$

And $Z_k$is LCS $\left(X\left[1....j-1\right],Y\left[1....j-1\right]\right)$followed by $z_k$.

That means,

Either role="math" localid="1657261518179" $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{}\mathbf{j}}\mathbf{=}\{\begin{array}{l}{d}_{i-1,j-1}+1;\mathrm{if}{x}_i=y_j\\ \max \left\{d_{i-1.j},d_{i.j-1}\right\};\mathrm{if}{x}_i\ne y_j\end{array}$

$$\begin{gathered} m=Lenght\left(x\right) \\ n=Lenght\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,j-1\right] \\ else \\ d\left[i,j\right]=d\left[i,j-1\right] \end{gathered}$$

return $d$

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