KMP

发表于 2015-01-23   |  

朴素的字符串查找的复杂度是 O(MN) 的，显然这里有很大的优化空间，KMP 算法 (Knuth-Morris-Pratt) 可优化至 O(M+N)。

引入 next[]

注：本文使用 Python 的 slice，即 [b:e] 为左闭右开

假设比较如下字符串（上行为 S，下行为 W）

CMP

当发现 ‘D’ 与 ‘X’ 不符时，并不需要重新比较 ‘BCABX……’ 和 ‘ABCABD……’ ，而是根据 W 本身的性质，紧接着比较 ‘X……’ 和 ‘CABD……’

可视为在匹配 S 的 ‘X’ 时，比较的字符从 ‘D’(W[5]) “跳至” ‘C’(W[2])
之所以可以这样比较，是因 为 W[0:2] == W[3:5] == ‘AB’

对于 W 中的所有字符，都有这样的允许“跳至”的位置，不妨记录至 next[]数组，例如对于上例的 W，next[5] = 2

参考上文，对于 W，我们这样定义 next[] 数组 

1
next[i] = max{j | W[0:j] == W[i-j:i] for -1 <= j < i}

next[] 的有效性

  1. 由 j 的 max 性质可保证查找不会遗漏匹配
  2. 查找匹配时，当 W[i] 不符时，跳至 W[next[i]] 继续比较即可

next[] 的推导

先进行简单考察

  1. 显然 next[0] = -1
  2. 当 next[i] = j 时（可知 W[0:j] == W[i-j:i]），考察 next[i+1]
    • 若 W[i] == W[j]
      则有 W[0:j+1] == W[i-j:i+1]
      猜想 next[i + 1] = j + 1
    • 若 W[i] != W[j]，记next[j] = k
      因为 W[0:k] == W[j-k:j] == W[i-k:i]
      猜想问题递归为 j = k 时的小问题

KMP

整理易得如下递归形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solve_next(W):
    def _solve_next(NEXT, W, i, j, k):
        # 前提1：W[0:j] == W[i-j:i]
        # 前提2：NEXT[j] = k, 可知 W[0:k] == W[j-k:j]
        # j 不参与运算，仅辅助证明
        if (k == -1) or (W[i] == W[k]):
            # NEXT[i + 1] >= k + 1
            # 又 NEXT[i + 1] <= k + 1，否则可推出 NEXT[j] > k，矛盾
            NEXT[i + 1] = k + 1
        else:
            # 显然满足前提1、2。(W[0:k] == W[j-k:j] == W[i-k:i])
            _solve_next(NEXT, W, i, k, NEXT[k])

    n = len(W)
    NEXT = [-1] * n
    for i in range(n - 1):
        _solve_next(NEXT, W, i, i, NEXT[i])
    return NEXT

不难转为递推形式

1
2
3
4
5
6
7
8
9
10
def solve_next(W):
    n, i, j = len(W), 0, -1
    NEXT = [-1] * n
    while i < n - 1:
        if (j == -1) or (W[i] == W[j]):
            NEXT[i + 1] = j + 1
            i, j = i + 1, j + 1
        else:
            j = NEXT[j]
    return NEXT

利用 next[] 即可高效查找匹配 

1
2
3
4
5
6
7
8
9
def search(W, S):
    NEXT = solve_next(W)
    i, j, m, n = 0, 0, len(W), len(S)
    while i < m and j < n:
        if (i == -1) or (W[i] == S[j]):
            i, j = i + 1, j + 1
        else:
            i = NEXT[i]
    return (i == m)

next[] 的小优化

对于下图情况，当 W 中后 ‘A’ 不符时，根本无需再匹配前 ‘A’ ，即 next[1] = -1比next[1] = 0 更高效

Advance

针对这样的情况，我们可以对 next[] 的定义稍稍修改 

1
next[i] = max{j | W[0:j] == W[i-j:i] and W[j] != W[i] for -1 <= j < i}

同样可先推导递归形式（ max 性质同样可归纳证明，已略去） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solve_next(W):
    def _solve_next(NEXT, W, i, j):
        # 前提：W[0:j] == W[i-j:i]
        if (j == -1) or (W[i] == W[j]):
            if W[i + 1] != W[j + 1]:  # 保证 NEXT 的性质
                NEXT[i + 1] = j + 1
            else:
                # ni, nj = i + 1, j + 1  # next_i, next_j, 已知 W[ni] == W[nj]
                # W[0:NEXT[nj]] == W[nj-NEXT[nj]:nj] == W[ni-NEXT[nj]:ni]
                # W[NEXT[nj]] != W[nj], 因此 W[NEXT[nj]] != W[ni]
                NEXT[i + 1] = NEXT[j + 1]
        else:
            # 满足前提。(W[0:NEXT[j]] == W[j-NEXT[j]:j] == W[i-NEXT[j]:i])
            _solve_next(NEXT, W, i, NEXT[j])

    n = len(W)
    NEXT = [-1] * n
    for i in range(n - 1):
        _solve_next(NEXT, W, i, NEXT[i])
    return NEXT

转为递推形式 

1
2
3
4
5
6
7
8
9
10
def solve_next(W):
    n, i, j = len(W), 0, -1
    NEXT = [-1] * n
    while i < n - 1:
        if (j == -1) or (W[i] == W[j]):
            i, j = i + 1, j + 1
            NEXT[i] = j if W[i] != W[j] else NEXT[j]
        else:
            j = NEXT[j]
    return NEXT
#Algorithm
Alias for cmd