扩展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("");
    }
}