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

Short answer

There are two approach of doing this problem:

1. Brute Force Method

Here, we will consider all the substring of string x=x₁x₂….x_n and check if how many of those possible substring of x can be found in string y=y₁y₂….y_m.

And also keeping track of maximum length of common substring.

But in this case, the run time is much greater then O(mn).

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 O(mn).

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 role="math" localid="1657260451767" $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 LCS $\left(X\left[1....j-1\right],Y\left[1....j-1\right]\right)$followed by $z_k$.

• If$x_i\ne y_i$

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}$

Algorithm

$$\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.