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 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鈮�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]鈮�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.