扩展kmp,循环问题
考察你对循环的理解。稍微有点绕但是没事,凭感觉往前走就好了
直接上模板
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int max_n = 2e6+100; int net[max_n], extend[max_n]; void getnext(char p[]) { register int a = 0;register int b = 0; int pn = strlen(p); net[0] = pn; for (register int i = 1;i < pn;++i) { if (i >= b || i + net[i - a] >= b) { if (i >= b) b = i; while (b < pn && p[b - i] == p[b]) ++b; net[i] = b - i; a = i; } else net[i] = net[i - a]; } } char s[max_n]; int main(){ int T;scanf("%d",&T); for (int tcase=1;tcase<=T;++tcase){ scanf("%s",s); int n = strlen(s); getnext(s); vector<int> res; for (int i=1;i<n;++i) if (net[i]>=n-i) res.push_back(i); res.push_back(n); printf("Case #%d: %d\n",tcase,(int)res.size()); printf("%d",res[0]); for (int i=1;i<res.size();++i)printf(" %d",res[i]);puts(""); } }