【字符串】跳来跳去的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]<<" "; } View Code

后记：

培训D2T3考到了KMP

上午也有讲思路

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

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

晚上又花了一点时间理解

打完了这个板子

转载于:https://www.cnblogs.com/BrokenString/p/9278288.html