【KMP模板】简单写个KMP~

本来easy的KMP

却一直过不了洛谷的模板题。。。

仔细一看原来在输出next数组时打的回车而不是空格。。。

身败名裂。。。

话说有个sunday貌似一般状况下比KMP快呢。。。去看看2333

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std;char a[1000010],b[10010]; int nextt[10010];int main() {scanf("%s%s",a+1,b+1);int la=strlen(a+1);int lb=strlen(b+1);int j=0;for(int i=2;i<=lb;i++){while(b[j+1]!=b[i]&&j) j=nextt[j];j+=(b[j+1]==b[i]);nextt[i]=j;}j=0;for(int i=1;i<=la;i++){while(j&&a[i]!=b[j+1]) j=nextt[j];j+=(a[i]==b[j+1]);if(j==lb) printf("%d\n",i-lb+1); }for(int i=1;i<=lb;++i)printf("%d ",nextt[i]);return 0; }

 

转载于:https://www.cnblogs.com/rir1715/p/6797554.html

总结

以上是生活随笔为你收集整理的【KMP模板】简单写个KMP~的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。