91影视

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 鈥榵鈥� and 鈥榶鈥�, 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:

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

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鈮�y_j\end{array}\end{array}$

$$\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]鈮�d\left[i,j-1\right]\right) \\ d\left[i,j\right]=d\left[i-1,j\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.