【字符串】跳来跳去的KMP匹配

原理：

不给予证明啦（懒得一批

但是代码中有给还算详细的注释

参考：https://www.cnblogs.com/yjiyjige/p/3263858.html

模板题：

洛谷P3375:

https://www.luogu.org/problemnew/show/P3375

代码：

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
char a[MAXN],b[MAXN];
int next[MAXN];
int la,lb,j; //j为所匹配到的最大的后缀的前缀最后一位 
int main()
{
    cin>>a+1;//从一开始存 
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for(int i=2;i<=lb;i++)//匹配匹配串 
    {
        while(j&&b[j+1]!=b[i])//判j不为零因为在第一位就不用往前找了
                              //如果不匹配就往前找 
        j=next[j];
        if(b[j+1]==b[i])//匹配就往下推 
        j++;
        next[i]=j;
    }
    j=0;
    for(int i=1;i<=la;i++)//匹配文本串 同上 
    {
        while(j&&b[j+1]!=a[i])
        j=next[j];
        if(b[j+1]==a[i])
        j++;
        if(j==lb)//找到一个匹配串输出位置 
        cout<<i-lb+1<<endl;
    }
    for(int i=1;i<=lb;i++)
    cout<<next[i]<<" ";
}

后记：

培训D2T3考到了KMP

上午也有讲思路

但是身为蒟蒻会思路不会代码啊

直接放弃了T3打前面的两题

晚上又花了一点时间理解

打完了这个板子