KMP字符串匹配算法是一种快速检索字符串的算法。本文探讨KMP算法原理及实现。注意下文中的字符串下标均从0开始。
        更新：2020.2.10优化排版。

KMP算法

        KMP匹配算法解决的问题是：如何快速判断字符串$A$（称主串）中是否包含字符串$B$（称模式串），如果包含，出现在哪些位置？
        该算法是从暴力匹配算法的不足改进而来。判断某个字符串中是否包含另一个字符串通常设置两个变量$i$、$j$，分别指向串$A$和串$B$的某个位置，依次检索。如果失配，则令$j=0$重新检索。这种算法时间复杂度$O(nm)$，不足在于每一次都重新检索，没有利用好之前匹配成功的信息。
        KMP算法便是在失配后的做法上进行了优化：当发生失配时，串$A$的检索位置$i$不动，$j$指向一个特定的数$next[j]$，之后再进行匹配。
        $next$数组是KMP算法的精髓，它储存的是模式串第$i$位（从$0$开始）失配后的跳转位置。要理解这个概念需要先理解前缀和后缀。对于字符串$abcd$：

  • 前缀：$a、ab、abc$
  • 后缀：$d、cd、bcd$

        这是很容易理解的。值得注意的是，这里的前后缀都不能包含字符串本身。

next数组

        如果一个长度为$p$的前缀与等长的后缀完全相同，则它们为一对相同前后缀。例如字符串$abcdab$中，由于前两个$ab$与后两个$ab$相同，因此这是一对相同前后缀。
        next数组定义即为：$next[i]$储存模式串的子串$[0，i-1]$的最长相同前后缀长度。由于$abcdab$的最长相同前后缀长度为$2$，因此对于字符串$abcdabe$，它的$next[6]=2$（6是末尾e的下标）。
        下面证明当$i$位失配时，跳转到$next[i]$的算法正确性。
        现在的匹配过程中，模式串第$i$位失配，说明第$0$~$i-1$位都是匹配的。这时我们要做的是固定主串不动，将模式串右移若干位，假设右移$p$位可以使模式串完全匹配，并假设第$i$位失配时，主串在第$j$位。
        原有的模式串首端指向主串第$j-i$位，右移后指向$j-i+p$位，这时应该有主串第$j-i+p$位等于模式串第$0$位，…，主串第$j-i+p+l-1$位等于模式串第$l-1$位（$l$为模式串长度）。
        下证$p ≥ i-next[i]$。假设$p < i-next[i]$：
        我们已经知道主串$[j-i+p，j-i+p+l-1]$部分与模式串$[0，l-1]$部分完全相同，那么主串$[j-i+p，j-1]$部分和模式串$[0，i-p-1]$部分也应该是相同的。
        由于第$i$位前是匹配的，所以主串$[j-i+p，j-1]$就是模式串$[p，i-1]$。那么模式串$[0，i-p-1]$=模式串$[p，i-1]$，于是我们找到了模式串第$0$到$i-1$位的一个相同前后缀，长度为$i-p$。
        然而根据假设：$i-p > i-(i-next[i]) = next[i]$。这与$next[i]$的最大性矛盾！于是$p≥i-next[i]$是正确的。
        $p≥i-next[i]$说明什么呢？说明至少要向右移动$i-next[i]$位才可能匹配，从而避免了很多次无意义的移动。从程序角度讲，模式串向右移动$i-next[i]$位就是将下标换成$next[i]$，然后与主串第$j$位比较。至此证明了算法正确性。

1
2
3
4
5
6
7
8
9
10
11
int i = 0, j = 0;//i是主串下标，j是模式串下标
    while (i < l1) {//l1是主串长度
        if (str1[i] == str2[j]) {//匹配
            if (j == l2 - 1) {
                cout << i - j + 1 << endl;
                if (j != 0)j = next[j];//完全匹配，输出位置，令j=next[j]（相当于假设这一位没有匹配以开始新的一轮）
                else i++;
            } else i++, j++;//否则继续比较
        } else if (j == 0)i++;//没有匹配并且j=0，i++以开始新的一轮
        else j = next[j];//j=next[j]进行跳转
    }

        KMP算法时间复杂度$O(n+m)$。下面是$next$数组的求法。
        next数组当然可以用最暴力的方法求出，但是也有更好的方法，那就是令模式串自己与自己匹配。
        易知$next[0]=next[1]=0$，现考虑能不能用前面已知的$next$值求后面的$next$值。
        假设要求$next[i]$。令$j=next[i-1]$，拿另一个相同模式串（称拷贝模式串）的第$j$位对齐到模式串第$i-1$位上。为什么要这样做呢？此时拷贝模式串的$[0，j-1]$位与模式串对应位置完全相同，并且容易知道如果将拷贝模式串左移几位，一定是不匹配的（证明与上面类似）。从这里开始进行匹配，如果$str[j]==str[i-1]$，那么匹配成功，$next[i]=j+1$；如果失配，注意到前面均匹配，所以可以采用跳转的方式：令$j=next[j]$，继续判断$str[j]$是否等于$str[i-1]$，只要出现相等的情况立即令$next[i]=j+1$并进行下一个$next$值的求解。如果直到$j=0$都没能匹配，那么$next[i]=0$。由于是从最大可能的长度找过来，所以结果一定是最大长度。
1
2
3
4
5
6
7
8
9
void findNext() {
    next[0] = next[1] = 0;
    int j = 0, i = 2;
    while (i < l2) {
        if (str2[j] == str2[i - 1])next[i++] = ++j;
        else if (j == 0)next[i++] = 0, j = 0;
        else j = next[j];
    }
}

        结合这两步即可得到完整的KMP匹配算法代码。

KMP算法的改进：nextval数组

        KMP算法已经十分优秀了，但还是有一些不足。例如当$i$位不匹配时，我们会选择从$i$位跳转到$next[i]$位，但是如果此时$next[i]$位对应的字符与$i$位相同，那么这一次显然也是不匹配的，之后就需要继续移动。当模式串很长且重复较多时，会引起很多无用的移动。
        这时我们希望$next$数组可以指向一个与第$i$位字符不同的一个位置，这就是$nextval$数组。$nextval$数组可以从$next$数组递推过来，只需要加上几行语句即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
void findNext() {
    next[0] = next[1] = nextval[0] = nextval[1] = 0;//初始化，全为0
    int j = 0, i = 2;
    while (i <= l2) {
        if (str2[j] == str2[i - 1]) {
            next[i] = ++j;
            if (str2[i] == str2[next[i]])nextval[i] = nextval[next[i]];//与next[i]对应相同时，就是nextval[next[i]]
            else nextval[i] = next[i];//否则就是next[i]
            ++i;
        } else if (j == 0)next[i++] = 0, j = 0;
        else j = next[j];
    }
}

        使用时直接将next数组换为nextval数组即可。但是这样需要注意一个问题：当需要统计模式串出现过的所有位置时，需要用next数组跳转。这是因为匹配成功时的跳转是一种“假设”，实际上是匹配的，如果用nextval跳转会造成少答案的现象。
1
2
3
4
5
6
7
8
9
10
11
int i = 0, j = 0;
while (i < l1) {
        if (str1[i] == str2[j]) {
            if (j == l2 - 1) {
                cout << i - j + 1 << endl;
                if (j != 0)j = next[j];//用next跳转
                else i++;
            } else i++, j++;
        } else if (j == 0)i++;
        else j = nextval[j];//换成nextval
    }

扩展kmp

        扩展kmp可以在线性复杂度下求某一个串的所有后缀与另一个串的最长公共前缀长度。
        模板：点这里，原理的话可以参考第一篇题解，这里就放一个板子。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

#define N 100005
using namespace std;
int nxt[N], extend[N];
string s, t;

inline void getNext() {
    nxt[0] = t.size();
    int now = 0, p0 = 1;
    while (t[now] == t[now + 1] && now + 1 < t.size())++now;
    nxt[1] = now;
    for (int i = 2; i < t.size(); i++) {
        if (i + nxt[i - p0] < nxt[p0] + p0)nxt[i] = nxt[i - p0];
        else {
            now = max(0, p0 + nxt[p0] - i);
            while (t[now] == t[i + now] && i + now < t.size())++now;
            nxt[i] = now, p0 = i;
        }
    }
}

inline void exKMP() {
    int now = 0, p0 = 0;
    while (s[now] == t[now] && now < s.size() && now < t.size())++now;
    extend[0] = now;
    for (int i = 1; i < s.size(); i++) {
        if (i + nxt[i - p0] < extend[p0] + p0)extend[i] = nxt[i - p0];
        else {
            now = max(0, extend[p0] + p0 - i);
            while (t[now] == s[i + now] && now < t.size() && i + now < s.size())++now;
            extend[i] = now, p0 = i;
        }
    }
}

int main() {
    cin >> s >> t;
    getNext(), exKMP();
    for (int i = 0; i < t.size(); i++)cout << nxt[i] << " ";
    cout << endl;
    for (int i = 0; i < s.size(); i++)cout << extend[i] << " ";
    return 0;
}