KMP

对与基础课还没刷完的同学（比如我），并且还没学KMP的同学（这个就没有我了，不然也写不了分享啊！），KMP肯定是大家的一大噩梦之一（就像我对图论的噩梦一样 （逃 ），今天cht就带大家消除恐惧（我也可能讲错啊，完了失信了，我估计大家看完可能消除不了，大家还是去看基础课吧。难啊）！

此处在此感谢抽风大佬，0凌大佬和季科大佬对我理解KMP的帮助！

一、准备工作。

1. 请先理解前缀和，具体请看分享： 前缀和与差分 DAY1-1
2. 请准备好你机智的大脑！
3. 请准备好燃烧你机智的大脑！
4. 请做好看n遍我的分享的准备。
5. 请做好骂我的分享讲的一点也不好的准备！！！

好，以上准备都做好了我们就可以开始今天的内容了。

二、KMP的基本算法与思想。

请看题目： ACWING.831 KMP字符串
然后请自行读题并回答一下问题：
1. 你应该知道什么是子串吧（否则请去语法课复习下）
2. 请你尝试写出暴力做法并判断这题会TLE
3. 请你思考后缀和前缀的概念。

暴力做法就是一点一点的匹配，毫无疑问时间复杂度是 O(n * m) ，相当于1e11，c++也就一秒算1e9，废话超时。

现在如果你保证你理解了后缀和前缀请继续看。
我们的KMP又是什么思路呢？
可能很多人看了前缀和的分享可能会想到：

会不会是要用初始化呢？

猜对了。

y总说过：

这就是我们KMP里最难的一个知识点：ne数组的作用。

那ne数组到底是干啥用的呢？
它是用来存两个个字符串相同字符的长度的（让我们想起了前缀和。）
那我们怎么查询呢？
如果前面的字符匹配，那继续往前看（不然呢？）
否则往后退，j = ne[j];。

到这里可能大家还不太明白，那我们在把上面的话变成人话说一下。
其实比如p=abcda，b=abc，那ne[b]应该存的就是我们的a。
然后看下abcda和a可以吗，显示a的是1，可以，j++，然后如此往复。

（可能有误，望大佬指导）
（可能有误，望大佬指导）
（可能有误，望大佬指导）

重要的事情说三遍！

在展示下0凌大佬和季科大佬所理解的KMP（ @0凌 @季科，你们要删随时私信我！！！）：
0凌大佬：

我的理解的是， ne数组存的就是当前这个字符串，相同的字符的最长长度，匹配的话，如果当前这个字符的后面一个和要匹配的字符串不匹配的话， 就去找前面一个和当前这个第一个字母匹配的。

orz

季科大佬：

记住next数组求法。就是某个串的最长后缀和前缀相同 。

%%%%%%%%

算了大家还是别看我的去问他们吧。。。

然后是激动的打代码环节！

三、板子与题解。

首先是ne数组的初始化：

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)
    {
        printf("%d ", i - n);
        j = ne[j];
    }
}

完整代码：

#include<iostream>
using namespace std;
const int N = 10000010;
int n, m, ne[N];
char s[N], p[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)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

本期分享到这里就要告一段落了，

这里是cht的全部分享！

我的算法分析可能有错误，忘谅解+指正（毕竟我多弱你们是知道的，我5天前刚学完KMP。）