KMP 算法

KMP 算法是利用重复片段进行优化的，无回溯的字符串匹配算法。

Update

（2021-10-14）：修正了预处理计算 $k$ 时未进行递推处理的错误。

回溯

TL;DR

暴力算法中存在不必要的向左回退比较。

暴力的字符串匹配算法会遇到回溯的情况，如下所示：

模式串 abc

    ababc
  1|^
  2|a^
! 3|ab^
! 4| ^

用模式串abc 匹配目标串ababc，在第 3 步中，先将模式串第 0 位对齐目标串第 0 位，模式串的前两位匹配成功，第 2 位匹配失败(3)，因此将模式串的第零位移动到目标串第 1 位重新对齐(4)，因而比较的位置回溯了，但由于(2)用模式串第 1 位 b 匹配目标串第 1 位 b 成功，(4)用模式串第 0 位 a 重新匹配目标串第 1 位必定失败，因此这样的回溯是妨害效率的。主要原因是，在回溯的过程中，原有的匹配成功信息没有被利用即被丢弃。

设模式串长度为 $m$ ，目标串长度为 $n$ ，最坏情况是每次都在模式串的最后一位匹配失败，即匹配 $m$ 次后失败，一直比较到模式串和目标串右对齐，模式串的第零位对齐在目标串第 $n - m$ 位，一共比较 $n - m + 1$ 次。由于 $n \geq m$ ，因而最坏时间复杂度是 $O (mn)$ 。

KMP 算法

TL;DR

KMP 算法利用了模式串中重复的片段，通过对齐这些片段实现不向左后退。

暴力算法中，每次在模式串第 $i$ 位和目标串第 $j$ 位匹配失败以后，模式串左端总是向右移动 1 位。而 KMP 算法的思路是，根据模式串的某种规律（将在下文分析），得出一个对应关系 $n e x t$ ，使得在模式串第 $i$ 位和目标串第 $j$ 位匹配失败以后，使得模式串的 $n e x t (i)$ 位和目标串 $j$ 位对齐，即模式串左端向右移动 $i - n e x t (i)$ 位，避免发生回溯。分析以下操作的例子：

模式串 abcdabd

    0   45
    abcdaabcda
! 1|abcda^
  2|    a^
    *   *

    01  456
    abcdabcdabd
! 3|abcdab^
  4|    ab^
    **  **

先看 $i \neq = 0$ 时的情况。

对于模式串 $p$ 匹配失败的第 $i$ 位之前的部分，即子串 $p_{i}^{'} = p_{0} p_{1} \dots p_{i - 1}$ ，我们希望找到 $p_{i}^{'}$ 中最长的一对完全相同的前缀和后缀，并把它的长度记作 $k_{i}$ ，即：

p_{0} p_{1} \dots p_{k_{i} - 1} = p_{i - k_{i}} p_{i - k_{i} + 1} \dots p_{i - 1}

并通过移位使得前缀左端移到原来后缀左端对应的位置，可以得到：

n e x t (i) = k_{i} (1)

如果找不到符合上述要求的一对前缀和后缀时，将模式串的左端直接对齐到匹配失败的一位即可。此时 $k_{i} = 0$ ，公式 $(1)$ 仍然成立。

如果 $i = 0$ ，也就是第 0 位已经匹配失败，则模式串的左端移到 $i + 1$ ，继续比较。令 $k_{0} = - 1$ ，公式 $(1)$ 仍然成立，只是 $p_{- 1}$ 没有意义。课本上基于此点把这两个混在一起了，多循环了一次，个人觉得有点还是分开处理比较好理解。

在 $j < n$ 时如果找到目标串中匹配模式串的子串，即满足 $i = m - 1$ 时匹配，则返回模式串左端位置 $j - i$ 。如果 $j = n$ ，说明目标串中不存在匹配模式串的字串，返回表示搜索无结果的值。

在搜索过程中， $j$ 不会减小（即不会发生回溯），递增的次数不会超过 $n$ 。 $j$ 递增的同时，一定伴随着 $i$ 递增， $i$ 在匹配失败时也会减小，但最多减小到 0，减小的次数不会多于增加的次数，因此最终 $i$ 递增的次数不会超过 $2 n$ 。所以，搜索部分的最坏时间复杂度是 $O (n)$ 。

模式串的预处理

TL;DR

通过递推的方法可以快速推出 $n e x t (i)$ 表，还可以再进行递归优化避免在移动模式串前后比较内容相同的情况。

问题的关键转移到了计算最长相同前后缀长度 $k_{i}$ 。这里利用递推会比较简单。

模式串 abaaa

    0  1  2  3  4
    a  b  a  a  a
0| -1  0  0

 |  *     ^
1| -1  0  0->1

 |  *  *  ^  ^
2| -1  0  0  1->2

...
 |  *  *  !
 |        ^  ^  !
3| -1  0  0  1  2->0

初始条件(0)是 $k_{0} = - 1$ 。

递推时，首先验证上一次验证中前缀末尾的下一位（把这个位置记作 $k$ ）和后缀末尾的下一位是否相等，如果相等（见上图），说明 $k_{i} = k_{i - 1} + 1$ 。如果不相等，相当于在前缀末尾的下一位（ $k$ ）处失配，因此应移动到 $n e x t (k)$ 处（见下图的百分号处，也就是 $n e x t (k)$ 变为了新的前缀末尾）继续尝试匹配，直至匹配成功，或 $k$ 迭代为负数。

模式串 abaab

    0  1  2  3  4
    a  b  a  a  b
0| -1  0  0  1
 
 |  *  !  ^  !
1| -1  0  0  1->?
 |     %

 |  *        ^
2| -1  0  0  1->1

这样就得到了 $n e x t$ ，但是还有优化的空间。

模式串 abab
   a  b  a  b
k -1  0  0  1

    abaabab
! 1|aba^
! 2|  a^
  3|   ^

在这个例子中，发现(1)匹配失败，(2)必定也匹配失败，两次比较的字符完全相同，多了一次无谓的比较，根本原因是 $s_{j} \neq = p_{i} = p_{k_{i}}$ ，使得移动模式串后，比较的字符没有变，还需要再次移动。因此，可以对 $k_{i}$ （当然也是 $n e x t (i)$ ）递推地优化：当 $p_{i} = p_{k_{i}}$ 时，令 $k_{i} = k_{k_{i}}$ ，或者写作“令 $n e x t (i) = n e x t (n e x t (i))$ ”，可能更方便理解。

对于上例，优化效果如下所示：

模式串 abab
    a  b  a  b
k  -1  0  0  1
k' -1  0 -1  0

    abaabab
! 1|aba^
  2|   ^

预处理过程中，对于递推部分的时间复杂度，外层循环中 $k$ 递增，内层循环中 $k$ 递减（恒有 $n e x t (k) < k$ ），由 $k \geq 0$ 且其初值为 $0$ 知递减总次数一定小于等于递增总次数 $m$ ；而优化中，由于优化到第 $i$ 项时第 $n e x t (i)$ 项已经优化过，因此无需递推。因此，预处理过程的时间复杂度是 $O (m)$ 。

结论

TL;DR

KMP 算法时间复杂度是 $O (m + n)$ 。

综上，KMP 算法的时间复杂度是 $O (m + n)$ ，小于暴力算法的 $O (mn)$ 。由于在实践中通常 $m ≪ n$ ，因此 KMP 算法的时间复杂度可以视为 $O (n)$ 。但是，由于 KMP 算法的优化基于重复片段，因此使用的字符集比较大时（比如汉语的字符集），重复片段出现的概率低，它的效率提升也有限。实践中，从尾部开始向左匹配并计算“坏字符”的另一个字符串匹配算法，BM 算法，效率更高，可以达到 $O (n)$ ，可以查看参考资料中的文章中的介绍。

Python 实现

NO_MATCH = -1

def kmp(p, s): # pattern 模式串, string 目标串
    m, n = len(p), len(s)
    i, j = 0, 0

    # 预处理
    nxt = [-1] # next 预处理表
    k = -1 # 上一次验证的前缀末尾
    for x in range(1, m):
        while k >= 0 and p[x-1] != p[k]:
            k = nxt[k] # 在 k 处失配
        k += 1 # k 处匹配成功，前缀长度可以递增 1
        
        if p[k] == p[x]:
            nxt.append(nxt[k]) # 优化
        else: nxt.append(k)

    # 比较
    while i < m and j < n:
        if p[i] == s[j]: # 匹配成功
            i += 1; j += 1
        else: # 匹配失败
            if nxt[i] == -1: # 向后移动1位
                i = 0; j += 1
            else:
                i = nxt[i] # 将nxt[i]位置和j位置对齐
    if i == m:
        return j - i # 返回子串的左端
    return NO_MATCH

参考资料

July，从头到尾彻底理解 KMP，2014
裘宗燕，数据结构与算法：Python 语言描述，2018