kmp next数组
这题莽一看似乎是用扩展kmp做的。
事实上确实,我们可以利用扩展kmp完成
但是其实我们利用kmp就可以做出来了
我们已经知道了kmp中的next数组的意义
next[n]意义为最长的公共前缀和后缀
然后我们想知道下一个公共前缀和后缀了
一点就透答案是next[next[n]]循环就好了,直到为0
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int max_n = 4e5+100; int n; char p[max_n]; int net[max_n]; void getnext(){ net[0]=-1;n=strlen(p);p[n]=500; for (int i=0,j=-1;i<n;){ if (j==-1||p[i]==p[j])net[++i]=++j; else j=net[j]; } } int main(){ while (~scanf("%s",p)){ vector<int> res; getnext();int cur = n; do{ res.push_back(cur); }while (cur = net[cur]); while (!res.empty()){ printf("%d ",res.back()); res.pop_back(); }puts(""); } }