LongestCommonSubsequence 最长公共子序列

问题

序列 $s$ 的子序列是原序列的子集，元素相对原序列的顺序不变。例如 $s = [1,2,3]$ 的子序列有

[1,2,3],[1,2],[1,3],[2,3],[1],[2],[3],[]

求两个序列 $s_{1}$ 和 $s_{2}$ 的最长公共子序列的长度。

设序列 $s$ 长度为 $n$ （数组从 $1$ 开始，范围 $[1,n]$ ）。设 $f(i,j)$ 为 $s_1 = [1,i]$ 和 $s_2 = [1,j]$ 的最长公共子序列的长度，则有状态转移方程：

f(i,j) = \begin{cases} 0 & (initialize) & i,j \in [0,n] \\ f(i-1,j-1)+1 & (loop) & i,j \in [1,n], s_1 [i] = s_2 [j] \\ max(f(i,j-1),f(i-1,j)) & (loop) & i,j \in [1,n], s_1 [i] \neq s_2 [j] \end{cases}

$(1)$ 初始化 $f(i,j) = 0$ ；

$(2)$ 若 $s_1 [i] = s_2 [j]$ ，则显然两个序列的这个部分是公共的，所以 $f(i,j)$ 在 $f(i-1,j-1)$ 的基础上加 $1$ ；

$(3)$ 若 $s_1 [i] \neq s_2 [j]$ ，则两个序列的这个部分不是公共的，所以 $f(i,j)$ 仍然保持之前的值，为了获取最大值我们会在 $f(i,j-1)$ 和 $f(i-1,j)$ 中选取最大的那个；

$f(n,n)$ 即为序列 $s_1$ 和 $s_2$ 的最长公共子序列的长度值。该算法的时间复杂度为 $O(n^2)$ 。

Last updated 6 years ago

问题

序列

s

的子序列是原序列的子集，元素相对原序列的顺序不变。例如

s = [1,2,3]

的子序列有

[1,2,3],[1,2],[1,3],[2,3],[1],[2],[3],[]

求两个序列

s_{1}

和

s_{2}

的最长公共子序列的长度。

解法

设序列

s

长度为

n

（数组从

1

开始，范围

[1,n]

）。设

f(i,j)

为

s_1 = [1,i]

和

s_2 = [1,j]

的最长公共子序列的长度，则有状态转移方程：

f(i,j) = \begin{cases} 0 & (initialize) & i,j \in [0,n] \\ f(i-1,j-1)+1 & (loop) & i,j \in [1,n], s_1 [i] = s_2 [j] \\ max(f(i,j-1),f(i-1,j)) & (loop) & i,j \in [1,n], s_1 [i] \neq s_2 [j] \end{cases}

(1)

初始化

f(i,j) = 0

；

(2)

若

s_1 [i] = s_2 [j]

，则显然两个序列的这个部分是公共的，所以

f(i,j)

在

f(i-1,j-1)

的基础上加

1

；

(3)

若

s_1 [i] \neq s_2 [j]

，则两个序列的这个部分不是公共的，所以

f(i,j)

仍然保持之前的值，为了获取最大值我们会在

f(i,j-1)

和

f(i-1,j)

中选取最大的那个；

f(n,n)

即为序列

s_1

和

s_2

的最长公共子序列的长度值。该算法的时间复杂度为

O(n^2)

。