详解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] \neq 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 \leq 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) = \emptyset     // 空串没有真字串

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

下标	-1	0	1	2	3	4	5	6	7	8	9
P [ ]	*	C	H	I	N	C	H	I	L	L	A
next [ ]	N/A	-1	0	0	0	0	1	2	3	0	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] \leq next[j] + 1 ————而且特别地，当且仅当 P[j] = P[t] 时如上图取等号。

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

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

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

那么一般地，若 P[j] \neq 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' 的最长 border t' 的长度。

样例输入

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

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

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