FZU-1901 Period II

fzufzufzuf，當p==3時，串的字尾fzufzufzuf與串fzufzufzuf的最長公共字首為7，根據題意，此時i取0~6（注意加粗部分）

fzufzufzuf

****fzufzufzuf（s[i]==s[i+p]，s[i]能比較部分也就隻有這行加粗部分）

是以隻需保證，串的字尾與串的最長公共字首==size(S) - p即可

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e6 + 6;
char T[N];
int Next[N], m;
void getNext()
{
    int a = 0, p = 0;
    Next[0] = m;
    for (int i = 1; i < m; i++)
    {
        if (i >= p || i + Next[i - a] >= p)
        {
            if (i >= p)
                p = i;

            while (p < m && T[p] == T[p - i])
                p++;

            Next[i] = p - i;
            a = i;
        }
        else
            Next[i] = Next[i - a];
    }
}
int main()
{
	int n, cnt = 1;
	scanf("%d", &n);
	while(n--){
		scanf("%s", T);
		m = strlen(T);
		getNext();
		queue<int> q;
		for(int i = 1; i < m; ++i){
			if(Next[i] == m - i){
				q.push(i);
			}
		}
		q.push(m);
		printf("Case #%d: %d\n", cnt, q.size());
		++cnt;
		while(!q.empty()){
			printf("%d", q.front());
			q.pop();
			if(!q.empty()){
				printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}