最长公共子序列（LCS）

前言
¶

一些定义：

公共子序列：对于给定数列 $A = {a_{1}, a_{2}, \dots, a_{M}}$ 和 $B = {b_{1}, b_{2}, \dots, b_{N}}$ ，若 $C = {c_{1}, c_{2}, \dots, c_{K}}$ 既是 $A$ 的子序列，又是 $B$ 的子序列，则称 $C$ 是 $A$ 和 $B$ 的公共子序列。
最长公共子序列：公共子序列中元素个数最多的那个。

最长公共子序列的长度
¶

动态规划
¶

记 $d p (i, j)$ 表示 ${a_{1}, a_{2}, \dots, a_{i}}$ 和 ${b_{1}, b_{2}, \dots, b_{j}}$ 的最长公共子序列的长度，不难得到转移方程：

d p (i, j) = max {d p (i - 1, j), d p (i, j - 1), d p (i - 1, j - 1) + f (i, j)}

其中：

f (i, j) = {\begin{aligned} 1, & a_{i} = a_{j} \\ 0, & a_{i} \neq a_{j} \end{aligned}

一个小优化

注意到 $a_{i} = a_{j}$ 时， $d p (i - 1, j - 1) + 1 ⩾ max {d p (i, j - 1), d p (i - 1, j)}$ ，则转移方程可以写成：

d p (i, j) = {\begin{aligned} d p (i - 1, j - 1) + 1, & a_{i} = b_{j} \\ max {d p (i, j - 1), d p (i - 1, j)}, & a_{i} \neq b_{j} \end{aligned}

时间复杂度： $O (M \cdot N)$
额外空间复杂度： $O (M \cdot N)$

./findLengthOfLCS.1.ts | 26 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
export function findLengthOfLCS(
  N1: number,
  N2: number,
  isEqual: (i: number, j: number) => boolean,
): number {
  if (N1 <= 0 || N2 <= 0) return 0

  const dp: number[][] = new Array(N1)
  for (let i = 0; i < N1; ++i) dp[i] = new Array(N2)

  dp[0][0] = isEqual(0, 0) ? 1 : 0
  for (let i = 1; i < N1; ++i) {
    dp[i][0] = dp[i - 1][0] | (isEqual(i, 0) ? 1 : 0)
  }
  for (let j = 1; j < N2; ++j) {
    dp[0][j] = dp[0][j - 1] | (isEqual(0, j) ? 1 : 0)
  }

  for (let i = 1; i < N1; ++i) {
    for (let j = 1; j < N2; ++j) {
      dp[i][j] = isEqual(i, j) ? dp[i - 1][j - 1] + 1 : Math.max(dp[i][j - 1], dp[i - 1][j])
    }
  }

  return dp[N1 - 1][N2 - 1]
}

转成最长上升子序列问题
¶

TIP

此算法当且仅当 $A$ 或 $B$ 中不存在重复元素时有效！

为方便表述，不妨记 $A$ 中不存在重复元素。算法过程如下：

用一个 TreeMap 或 HashMap 在 $O (M)$ 或 $O (M \log M)$ 的复杂度下求出映射： $f : a_{i} \to i$ .

calc-map.ts

1
2
const f: Map<number, number> = new Map(A.length)
for (let i = 0; i < A.length; ++i) f.set(A[i], i)

通过映射 $f$ 将数组 $B$ 中的元素映射成 $B^{'}$ ，并过滤掉所有 $A$ 中未出现的元素，这一步的复杂度和第一步相同，同为 $O (M)$ 或 $O (M \log M)$ .
calc-b-prime.ts
1 2 3 4 5 const B2: number[] = [] for (const b of B) { const idx = f.get(b) if (idx !== undefined) B2.push(idx) }
举个栗子，不妨假设 $A = {3, 2, 1, 7, 5}$ ， $B = {2, 1, 1, 3, 7, 8}$ ；则可以求出映射 $f$ 为：
$f : {3, 2, 1, 7, 5} \to {1, 2, 3, 4, 5}$
接着，可以求出 $B^{'} = {2, 3, 3, 1, 4}$ ，其中 $B_{6} = 8$ 未在 $A$ 中出现，故直接过滤掉。
对 $B^{'}$ 求一次最长上升子序列，得到的即为 $A$ 和 $B$ 的最长公共子序列，这一步的复杂度为 $O (N \log N)$ .
do-lcs.ts
1 return findLengthOfLIS(B2.length, (i, j) => B[i] - B[j])

综上，总复杂度为：

时间复杂度： $O (M \log M + M \log M + N \log N)$
空间复杂度为： $O (M + N)$

最小字典序最长公共子序列
¶

沿着 dp[i][j] === dp[i-1][j-1] + 1 的路径可以找到一个最长公共子序列，如果从 $0$ 开始枚举 $i$ 或 $j$ 则可以分别找到以第一个序列为base和以第二个序列为base的最小字典序最长公共子序列。

./findMinLexicographicalLCS.ts | 39 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Find the least lexicographical order of the longest common subsequences.
 */
export function findMinLexicographicalLCS(
  N1: number,
  N2: number,
  isEqual: (x: number, y: number) => boolean,
): number[] {
  if (N1 <= 0 || N2 <= 0) return []

  const dp: number[][] = new Array(N1)
  for (let i = 0; i < N1; i += 1) dp[i] = new Array(N2)

  dp[0][0] = isEqual(0, 0) ? 1 : 0
  for (let i = 1; i < N1; i += 1) {
    dp[i][0] = dp[i - 1][0] | (isEqual(i, 0) ? 1 : 0)
  }
  for (let j = 1; j < N2; j += 1) {
    dp[0][j] = dp[0][j - 1] | (isEqual(0, j) ? 1 : 0)
  }

  for (let i = 1; i < N1; i += 1) {
    for (let j = 1; j < N2; j += 1) {
      dp[i][j] = isEqual(i, j) ? dp[i - 1][j - 1] + 1 : Math.max(dp[i][j - 1], dp[i - 1][j])
    }
  }

  const paired: number[] = new Array(N2).fill(-1)
  for (let len = dp[N1 - 1][N2 - 1], i = N1 - 1; len > 0; len -= 1) {
    for (let j = 0; j < N2; j += 1) {
      if (dp[i][j] === len) {
        while (i >= 0 && dp[i][j] === len) i -= 1
        paired[j] = i + 1
        break
      }
    }
  }
  return paired
}

Text Diff
¶

实际上只需要求出一个最小字典序的最长公共子序列，在此基础上将原序列patch上去就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 核心代码
import { findMinLexicographicalLCS } from '@algorithm.ts/lcs'

// For simplicity, we can assume that the token is of type string
type T = string
const lTokens: T[] = [] // Omit the definition of lTokens.
const rTokens: T[] = [] // Omit the definition of rTokens.
const isEqual = (x: number, y: number): boolean => lTokens[x] === rTokens[y]

const paired: number[] = findMinLexicographicalLCS(N1, N2, isEqual)
const pieces: Array<ITextDiffPiece<T>> = []
for (let i = 0, j = 0, k: number; j < N2; ) {
  for (k = j; k < N2 && paired[k] === -1; ) k += 1
  if (k < N2) {
    for (; i < paired[k]; i += 1) {
      pieces.push({ type: 'REMOVED', token: lTokens[i] })
    }
    for (; j < k; j += 1) {
      pieces.push({ type: 'ADDED', token: rTokens[j] })
    }
    pieces.push({ type: 'COMMON', token: rTokens[k] })
    i += 1
    j += 1
  } else {
    for (; i < N1; i += 1) {
      pieces.push({ type: 'REMOVED', token: lTokens[i] })
    }
    for (; j < N2; j += 1) {
      pieces.push({ type: 'ADDED', token: rTokens[j] })
    }
    break
  }
}

之后只需要合并 pieces （相同类型的紧邻 token 合并在一起）就好了。需要注意的是，对于 lTokens 或 rTokens 为空的情况需要做一个特判：

1
2
if (lTokens.length <= 0) return [{ type: 'ADDED', value: rTokens.join('') }]
if (rTokens.length <= 0) return [{ type: 'REMOVED', value: rTokens.join('') }]

前言¶

最长公共子序列的长度¶

动态规划¶

转成最长上升子序列问题¶

最小字典序最长公共子序列¶

Text Diff¶

Related¶