最长公共子序列（LCS）

前言
¶

一些定义：

公共子序列：对于给定数列 $A=\lbrace a_1,a_2,\cdots,a_M \rbrace$ 和 $B=\lbrace b_1,b_2,\cdots,b_N \rbrace$，若 $C=\lbrace c_1,c_2,\cdots,c_K \rbrace$ 既是 $A$ 的子序列，又是 $B$ 的子序列，则称 $C$ 是 $A$ 和 $B$ 的公共子序列。
最长公共子序列：公共子序列中元素个数最多的那个。

最长公共子序列的长度
¶

动态规划
¶

记 $dp(i,j)$ 表示 $\lbrace a_1, a_2, \cdots, a_i \rbrace$ 和 $\lbrace b_1, b_2, \cdots, b_j \rbrace$ 的最长公共子序列的长度，不难得到转移方程：

$$dp(i,j) = \max \lbrace dp(i-1, j), \; dp(i, j - 1), \; dp(i-1, j-1) + f(i, j) \rbrace$$

其中：

$$f(i,j) = \left\lbrace \begin{aligned} &1, &a_i=a_j\\ &0, &a_i \neq a_j\\ \end{aligned} \right.$$

一个小优化

注意到 $a_i = a_j$ 时，$dp(i-1, j-1) + 1 \geqslant \max \lbrace dp(i, j-1), dp(i-1, j) \rbrace$，则转移方程可以写成：

$$dp(i,j) = \left\lbrace \begin{aligned} &dp(i-1, j-1) + 1, &a_i = b_j \\ &\max\lbrace dp(i,j-1), dp(i-1, j) \rbrace, &a_i \neq b_j\\ \end{aligned} \right.$$

时间复杂度： $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 \rightarrow 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 = \lbrace 3, 2, 1, 7, 5 \rbrace$， $B = \lbrace 2, 1, 1, 3, 7, 8 \rbrace$；则可以求出映射 $f$ 为：
$$f: \lbrace 3, 2, 1, 7, 5 \rbrace \rightarrow \lbrace 1, 2, 3, 4, 5 \rbrace$$
接着，可以求出 $B' = \lbrace 2, 3, 3, 1, 4 \rbrace$，其中 $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¶