详解KMP算法（上）

在涉及字符串的众多实际应用中，模式匹配是最常用的一个操作。

根据具体应用的要求不同，串匹配问题可以多种形式呈现。

• 有些场合属于模式检测（pattern detection）问题：

  我们只关心是否存在匹配而不关心具体的匹配位置，比如垃圾邮件的检测。

• 有些场合属于模式定位（pattern location）问题：

  若经判断的确存在匹配，则还需确定具体的匹配位置，比如带毒程序的鉴别与修复。

• 有些场合属于模式计数（pattern counting）问题：

  若有多处匹配，则统计出匹配子串的总数，比如网络热门词汇排行榜的更新。

• 有些场合则属于模式枚举（pattern enumeration）问题：

  在有多处匹配时，报告出所有匹配的具体位置，比如网络搜索引擎。

形式化的，将其描述为：

如何在字符串数据中，检测和提取以字符串形式给出的某一局部特征。

考虑如下需求：

给定一个文本串 $S$ 和一个模式串 $P$，在 $S$ 中找出 $P$ 第一次出现的位置。

1. 暴力匹配算法

这是最经典的考察字符串匹配算法的问题，对于这种需求，我们可以考虑使用暴力匹配算法，这是最直接的算法。

1.1 算法描述

即从 $S$ 的第一个字符开始，逐个与 $P$ 的字符进行比较，如果匹配成功，则继续比较下一个字符，否则，从 $S$ 的下一个字符开始重新比较。

1.2 算法实现

对此，我们可以给出两个版本的代码实现：

int match(string s, string p) // 串匹配算法
{
    int lens = s.length(); // 文本串长度
    int lenp = p.length(); // 模式串长度
    int i = 0, j = 0;      // i指向文本串，j指向模式串，代表当前比对字符的位置
    while (i < lens && j < lenp)
    {
        if (s[i] == p[j]) // 若匹配
        {
            i++;
            j++; // 同时后移，跳转至下一个字符
        }
        else // 若不匹配
        {
            i -= j - 1; // 文本串回退
            j = 0;      // 模式串复位
        }
    }
    return i - j; // 返回匹配位置
}

以上代码借助整数 $i$ 和 $j$ ，分别指示 $S$ 和 $P$ 中当前接受比对的字符 $S[i]$ 与 $P[j]$。若当前字符对匹配，则 $i$ 和 $j$ 同时递增以指向下一对字符。一旦 $j$ 增长到 $m$ 则意味着发现了匹配，即可返回 $P$ 相对于 $S$ 的对齐位置 $i-j$。一旦当前字符对失配，则 $i$ 回退并指向 $S$ 中当前对齐位置的下一字符，同时 $j$ 复位至 $P$ 的首字符处，然后开始下一轮比对。

int match(string s, string p)
{
    int lens = s.length(); // 文本串长度
    int lenp = p.length(); // 模式串长度
    int i = 0;             // 与模式串首字符的对其位置
    int j;                 // 当前接受比对的字符的位置
    for (i = 0; i < lens - lenp + 1; i++)
    {   // 文本串从第 i 个字符开始，与模式串中对应的字符逐个比对
        for (j = 0; j < lenp; j++)
        {
            if (p[i + j] != s[j])
            {
                break;  // 若失配，模式串整体右移一个字符，再做一轮比对
            }
        }
        if (j >= lenp)
        {
            break;  // 找到匹配子串
        }
    }
    return i;
}

如上代码借助整数 $i$ 指示 $P$ 相对于 $S$ 的对齐位置，且随着 $i$ 不断递增，对齐的位置逐步右移。在每一对齐位置 $i$ 处，另一整数 $j$ 从 $0$ 递增至 $m-1$，依次指示当前接受比对的字符为 $S[i+j]$ 与 $P[j]$。因此，一旦发现匹配，即可直接返回当前的对齐位置 $i$。

1.3 时间复杂度

为了方便分析说明，我们令 $n$ 为 $S$ 的长度，$m$ 为 $P$ 的长度。

从理论上讲，暴力算法最多迭代 $n-m+1$ 轮，且各轮至多需要进行 $m$ 次比对，故总共只需要做不超过 $(n-m+1)\times m$ 次比对。那么，这种最坏的情况的确会发生吗？答案是肯定的。

我们不妨来构造一种极端情况，考虑如下的 $S$ 与 $P$：

S: 000000000……0000001
P: 0001

考虑如上情况，无论采用上述哪个版本的暴力算法，都需要做 $n-m+1$ 轮迭代，且各轮都需要做 $m$ 次比对，故总共需要做 $(n-m+1)\times m$ 次字符比对，其中成功的和失败的都各有 $(m-1)\times (n-m+1)$ 和 $n-m-2$ 次。因为 $m$ 远远小于 $n$，故这种极端情况下的时间复杂度为 $O(nm)$。

2. KMP 算法

2.1 构思

上一节的分析表明，暴力算法在最坏的情况下所需时间，为文本串长度与模式串长度的乘积，很有必要改进。为此，我们不妨从分析以上最坏情况入手。

稍加观察不难发现，问题主要在于这里存在着大量的局部匹配：每一轮的 $m$ 次比对中，仅最后一次可能失配。而一旦发现失配，文本串、模式串的字符指针都要回退，并从头开始下一轮尝试。

简单模拟一下暴力算法的匹配过程，统计文本串中各个字符被比对的次数。不难发现，原因就在于 $S$ 回退，$P$ 复位之后，此前比对过的字符，将再次参与比对。于是，只要局部匹配很多，效率必将很低。

实际上，重复的比对操作没有必要。既然我们已经掌握了 $S$ 中 $[i-j,j)$ 的全部信息，也就是说它具体是由那些字符所构成的，而这类信息，完全可以为后续的各步比对所利用。

还是回到刚才那个例子，考察在一次迭代中失败的那次比对，尽管这次比对是失败的，但却意味着在此前我们已经获得足够多次成功的匹配，在这个例子中也就是之前的 $0-0$ 匹配，也就是说在主串中那个对应的子串，完全是由 $0$ 构成的。之前的暴力算法没有注意到并且充分利用这一点，如果将这个特性利用起来，我们就可以每次大幅度地向右滑动，从而降低复杂度。

…… |0|0 0 0 0 0|0 0 0……
   |0|0 0 0 0 0|1
   | |0 0 0 0 0|0 1

对于如上情况，我们可以发现，即便下一轮迭代只能将模式串整体右移一个字符，但相较于暴力算法，中间那五个连续的 $0$，也就是第三行中模式串的 $[0,5)$ 这个前缀，都不用再继续比对了，我们只需要从竖线右边开始比对即可。

如此一来，$i$ 将完全不必回退！

• 比对成功，则与 $j$ 同步前进一个字符。
• 否则，$j$ 更新为某个更小的 $t$，并继续比对。

我们再举出一个更为复杂的情况，考察如下的文本串和模式串：

这里的一轮迭代，首次失配于 $E$ 和 $O$ 之间的失配，这里并不需要亦步亦趋地右移模式串，而是可以大胆地将其后移 $3$ 个字符，此前两个对其位置都可以排除掉。

如果一个位置值得对其，那么它的首字符必定是 $R$ 而非 $E$ 或者 $G$，所以下一轮直接移动到了 $R$ 的位置。

2.2 next 表

一般地，如下图所示，假设前一轮比对终止于 $S[i]\ne P[j]$。按以上构想，指针 $i$ 不必回退，是将 $S[i]$ 与 $P[t]$ 对齐并开始下一轮比对。那么，$t$ 应该取什么值呢？

由图可见，经过此前一轮的比对，已经可以确定匹配的范围应为：

$$P[0,j)=S[i-j,i)$$

于是，若模式串 $P$ 经适当右移之后，能够与 $S$ 的某一（包括 $S[i]$ 在内的）子串完全匹配，则一项必要条件就是：

$$P[0,t)=S[i-t,i)=P[j-t,j)$$

亦即,在 $P[0,j)$ 中长度为 $t$ 的真前缀，应与长度为 $t$ 的真后缀完全匹配，故 $t$ 必来自集合：

$$N(P,j)=0\le t<j|P[0,t)=P[j-t,j)$$

一般地，该集合中可能包含多个这样的 $t$。但需要特别注意的是，其中具体由哪些 $t$ 值构成，仅取决于模式串 $P$ 以及前一轮比对的首个失配位置 $P[j]$，而与文本串 $S$ 无关！

从图中还可以看出，若下一轮比对将从 $S[i]$ 与 $P[t]$ 的比对开始，这等效于将 $P$ 右移 $j-t$ 个单元，位移量与 $t$ 成反比。因此，为保证 $P$ 与 $S$ 的对齐位置（指针 $i$ ）绝不倒退，同时又不致遗漏任何可能的匹配，应在集合 $N(P,j)$ 中挑选最大的 $t$ 。也就是说，当有多个值得试探的右移方案时，应该保守地选择其中移动距离最短者。于是，若令

$$next[j]=\max (N(P,j))$$

则一旦发现 $P[j]$ 与 $S[i]$ 失配，即可转而将 $P[next[j]]$ 与 $S[i]$ 对齐，开始下一轮比对。

既然集合 $N(P,j)$ 仅取决于模式串 $P$ 以及失配位置 $j$，而与文本串无关，作为其中的最大元素，$next[j]$ 也必然具有这一性质。于是，对于任一模式串 $P$，不妨通过预处理提前计算出所有位置 $j$ 所对应的 $next[j]$ 值，并整理为表格以便此后反复查询。

2.3 KMP 算法

将上述思想整理为算法，即可得到 KMP 算法。

这里假定可以通过 buildNext() 函数构造出模式串 $P$ 的 next 表。对照先前第一个暴力算法，只是在 else 分支对失配的情况处理手法有所不同，这也是 KMP 算法的精髓所在。

int match(string s, string p) // KMP 算法
{
    int *next = buildNext(p);    // 构造 next 表
    int lens = s.length();       // 文本串长度
    int lenp = p.length();       // 模式串长度
    int i = 0, j = 0;            // i 指向文本串，j 指向模式串
    while (j < lenp && i < lens) // 自左向右逐个比对字符
    {
        if (0 > j || s[i] == p[j]) // 若匹配，或 p 已移出最左侧（两个判断的次序不可交换）
        {
            i++; // 则转到下一字符
            j++;
        }
        else // 否则
        {
            j = next[j]; // p 右移（注意：文本串不用回退）
        }
    }
    delete[] next; // 释放 next 表空间
    return i - j;
}

提示：若使用万能头且声明形如 vector<int> next 的数组，则数组名称不能使用 next，会与 stl_iterator_base_funcs.h 中的保留关键字 next 冲突.

2.4 next[0] = -1

不难看出，只要 $j>0$ 则必有 $0\in N(P,j)$。此时 $N(P,j)$ 非空，从而可以保证“在其中取最大值”这一操作的确可行。但反过来，若 $j=0$，则即便集合 $N(P,j)$ 可以定义，也必是空集。

形式化的：

只要 $j>0$，必有 $0\in N(P,j)$     // 空串是任何非空串的真字串
但若 $j=0$，则有 $N(P,0)=\varnothing$     // 空串没有真字串

此种情况下，又该如何定义 $next[j=0]$ 呢？

考虑上述的实例，假象地加一个通配符 $p[-1]$。即在传匹配的过程中，比方说某一轮遇到首对字符比对就失配，则应将 $P$ 右移一个字符，然后启动下一轮比对。

因此如上表所示，不妨假象地在 $P[0]$ 左侧“附加”一个 $P[-1]$，且该字符与任意字符都是匹配的。就实际效果而言，这一处理方法完全等同于“令 $next[0]=-1$”。

对于 $next[0]=-1$这种情况，自己造一组样例带入上面的代码手动模拟一下，不难理解，所以在这里笔者也就不做具体演示了。

2.5 next[j + 1]

那么，已知 $next[0,j]$，如何才能快速递推地计算出 $next[j+1]$？

若 $next[j]=t$，则意味着在 $P[0,j)$ 中，自匹配的真前缀和真后缀的最大长度为 $t$，故必有 $next[j+1]\le next[j]+1$ ————而且特别地，当且仅当 $P[j]=P[t]$ 时如上图取等号。

以上图为例，我们来证明一下那个结论。

以左边的红线为界，可以发现，下面的 $P$ 的前缀，与上面的子串是完全匹配的，因此如果 $P[j]$ 与他的继承者也是相等的，那么这种子匹配的长度就会增加一个单位。所以 next 表中的第 $j+1$ 项也自然地应该在此前的第 $j$ 项的基础上再递增一个单位。这样也就证明了如上当且仅当中第一个当的方向。

为了进而证明仅当，我们只需考虑 $P[j]$ 与他的替代者不相等的情况，比如后者为 $Y$。

那么一般地，若 $P[j]\ne P[t]$，又该如何得到 $next[j+1]$？

此种情况下，由 next 表的功能定义，$next[j+1]$ 的下一候选者应该依次是 $next[next[j]]+1$，$next[next[next[j]]]+1$，……

因此，只需反复用 $next[t]$ 替换 $t$（即令 $t=next[t]$），即可按优先次序遍历以上候选者；一旦发现 $P[j]$ 与 $P[t]$ 匹配（含与 $P[t=-1]$ 的通配），即可令 $next[j+1]=next[t]+1$。既然总有 $next[t]<t$，故在此过程中 $t$ 必然严格递减；同时，即便 $t$ 降低至 $0$，亦必然会终止于通配的 $next[0]=-1$，而不致下溢。如此，该算法的正确性完全可以保证。

2.6 构造 next 表

按照以上思路，可以实现next表构造算法如下代码所示。

int *buildNext(string p) // 构造模式串 P 的 next 表
{
    int lenp = p.length();
    int j = 0;              // “主”串指针
    int *N = new int[lenp]; // next 表
    int t = N[0] = -1;      // 模式串指针
    while (j < lenp - 1)
    {
        if (0 > t || p[j] == p[t]) // 匹配
        {
            j++;
            t++;
            N[j] = t;
        }
        else // 失配
        {
            t = N[t];
        }
    }
    return N;
}

我们会发现上述构造算法中，匹配的部分与 KMP 主算法几乎完全一致，实际上按照上述的分析，这一构造过程完全等效于模式串进行自我匹配，所以两个算法在形式上近似不足为怪。

3. 例题演示

我们以 洛谷 P3375 【模板】KMP字符串匹配 为例，来演示一下 KMP 算法的使用。

题目描述

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s^{\prime }$ 的最长 border $t^{\prime }$ 的长度。

样例输入

ABABABC
ABA

样例输出

1
3
0 0 1

样例解释

。

对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$。

题目分析

这一题和文章开头给出的需求还是有一定出入的，它有可能多次匹配，所以前文给出的代码不能满足需求，需要进行调整，同时题目还要求输出 border 数组。

那么就要微调一下算法的模板，同时要注意 next 数组并不等同于 border 数组。

下面给出代码实现。

#include <bits/stdc++.h>

using namespace std;

vector<int> Next;   // 这里要注意命名不可以为 next，会与库函数冲突

void buildNext(string p)    // 构造模式串 P 的 next 表
{
    Next.resize(p.length() + 1);    // 注意这里要多分配一个空间
    Next[0] = -1;                   // 因为首项为 -1
    int i = 0, j = -1;              // 同时又要保证求出 border 数组
    while (i < p.length())
    {
        if (0 > j || p[i] == p[j])
        {
            i++;
            j++;
            Next[i] = j;
        }
        else
        {
            j = Next[j];
        }
    }
}

vector<int> ans;        // 保存匹配位置

void match(string s, string p)
{
    buildNext(p);
    int lens = s.length();
    int lenp = p.length();
    int i = 0, j = 0;
    while (i < lens && j < lenp)
    {
        if (0 > j || s[i] == p[j])
        {
            i++;
            j++;
            if (j == lenp)
            {   // 匹配成功，记录位置 同时 j = Next[j] 以便继续匹配
                ans.push_back(i - j + 1);
                j = Next[j];
            }
        }
        else
        {
            j = Next[j];
        }
    }
}

int main()
{
    string s, p;

    cin >> s >> p;

    match(s, p);

    for (int i = 0; i < ans.size(); i++)    // 输出匹配位置
    {
        cout << ans[i] << endl;
    }

    for (int i = 1; i < Next.size(); i++)   // 输出 border 数组
    {
        cout << Next[i] << " ";
    }

    return 0;
}

实际上，本篇文章目前的 KMP 算法版本还不是最优的，在某一方面还是存在一些细微的瑕疵，可以针对这个缺陷对它再做改进，那么具体的复杂度分析和改进将在下一篇文章中进行介绍，敬请期待。

在此也感谢邓俊辉老师公开的精美课件，为本文的创作提供了很大的便利。

如果发现本文有缺陷或者错误，欢迎在评论区指出，我会及时修改。