算法学习-KMP模式匹配

概述

给定一个文本 $A$ 和一个字符串 $B$ ，我们可以利用 KMP 算法尝试找到并展示 $B$ 在 $A$ 中的所有出现（occurrence）。

模板

预处理前缀函数

预处理出字符串 $B$ 的前缀函数 $next$ 数组，其中 $next[i]$ 为既是子串 $B[1…i]$ 的前缀同时也是该子串的后缀的最长真前缀长度。一个字符串的真前缀是其前缀但不等于该字符串本身。根据定义， $next[1]=0$ 。

算法流程

1. 在循环中以 $i=2$ 到 $i=n$的顺序计算前缀函数 $next[i]$ 的值。（$next[1]$ 被赋值为0）
2. 为了计算当前的前缀函数值 $next[i]$，我们令变量 $j$ 表示右端点位于 $i-1$ 的最长匹配前后缀的长度。初始时 $j=next[i-1]$ 。
3. 通过比较 $B[j+1]$ 和 $B[i]$ 来检查长度为 $j+1$ 的后缀是否同时也是一个前缀。如果二者相等，那么置 $next[i]=j+1$，否则减少 $j$ 至 $next[j]$ 并重复该过程。
4. 如果 $j=0$ 并且仍没有任何一次匹配，则置 $next[i]=0$ 并移至下一个下标 $i+1$ 。

F.A.Q

算法流程中的步骤三，为什么要将 $j$ 减少至 $next[j]$ ？

考虑我们正在计算的 $next[i]$ 。我们要使 $k$ 最大化，并且保证 $B[1…k]$ 与 $B[i-k+1…i]$ 相等。将其拆成两部分看，我们需要在 $B[1…k-1]$ 与 $B[i-k+1…i-1]$ 相等的同时，保证 $B[k]=B[i]$ ，且 $k$ 取到最大值。

不难发现，如果只需要最大化 $k-1$ 使得 $B[1…k-1]$ 与 $B[i-k+1…i-1]$ 相等，我们可以很快得出答案。回顾一下前缀函数的定义即可发现，记 $j$ 为 $next[i-1]$，则此时的 $j$ 即为我们需要最大化的 $k-1$ 的值。如果这时又恰好满足 $B[j+1]=B[i]$ ，则我们需要最大化的 $k$ 即为 $j+1$ 。

然而此时如果不能满足 $B[j+1]=B[i]$ ，我们就只能考虑减小 $j$ 的值。在减小 $j$ 值的同时，我们要始终保证减小后的 $j’$ 满足 $B[1…j’]=B[j-j’+1…j]$ 。

结合上图不难看出，要使得 $B[1…j’]=B[i-j’…i-1]$，即保证 $B[1…j’]=B[j-j’+1…j]$ 。而 $j’$ 的确定也十分简单，再次结合前缀函数的定义可得， $j’$ 的取值应为 $next[j]$ 。

代码实现

1
2
3
4
5
6

next[1] = 0;
for (int i = 2, j = 0; i <= M; ++i) {
    while (j > 0 && B[i] != B[j + 1]) j = next[j];
    if (B[i] == B[j + 1]) j++;
    next[i] = j;
}

在目标串中查找子串

计算出 $f$ 数组，其中 $f[i]$ 为既是子串 $B[1…i]$ 的前缀同时也是子串 $A[1…i]$ 的后缀的最长前缀长度。（注意这里不一定是真前缀）在预处理前缀函数的过程中，相当于 $B$ 串与自己本身做了一次模式匹配，因此此处的算法流程与上一个操作十分类似。

算法流程

1. 在循环中以 $i=1$ 到 $i=n$的顺序计算 $f[i]$ 的值。
2. 为了计算当前的 $f[i]$ ，我们令变量 $j$ 表示右端点位于 $i-1$ 的最长匹配前后缀的长度。初始时 $j=f[i-1]$ 。
3. 通过比较 $B[j+1]$ 和 $A[i]$ 来检查 $B$ 串中长度为 $j+1$ 的前缀是否也是 $A$ 串中长度为 $j+1$ 的后缀。如果二者相等，那么置 $f[i]=j+1$，否则减少 $j$ 至 $next[j-1]$ 并重复该过程。
4. 如果 $j=0$ 并且仍没有任何一次匹配，则置 $f[i]=0$ 并移至下一个下标 $i+1$ 。
5. 如果 $j=M$，即找到 $B$ 在 $A$ 中的一次出现。

代码实现

1
2
3
4
5
6

for (int i = 1, j = 0; i <= N; ++i) {
    while (j > 0 && A[i] != B[j + 1]) j = next[j];
    if (A[i] == B[j + 1]) j++;
    f[i] = p;
    // if (f[i] == M) do something... 
}