KMP 字符串匹配

前缀表 ne[] :

定义：

假设长度为 的模式串 中 的所有以第 位开头的前缀用 表示（其中 表示前缀的长度）， 的所有以第 位结尾的后缀用 表示（含义同上）

那么

example :

假设模式串 ，那就有

正确性：

假设当前匹配到了文本串 的第 位，模式串 的第 位，使得 。这时将 向后移动，使得 的第 位与 的第 位匹配。

假设移动更小的距离使得 可以与 完全匹配，设此时令 的第 位 与 的第 位匹配，那么一定有 的 与 的 匹配，而此时已经有 的 与 的 匹配，所以 的 与 一定相等，与 的定义相矛盾。

所以这样的移动一定是最优的，可以排除最多的无效匹配过程。

code :

以 AcWing 831 为例

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 1000010;

char s[M], p[N];
int n, m;
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for(int i = 2, j = 0; i <= n; i ++ )
    {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for(int i = 1, j = 0; i <= m; i ++ )
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++ ;
        if(j == n)
        {
            cout << i - n << ' ';
            j = ne[j];
        }
    }

    return 0;
}