题目链接:http://acm.fzu.edu.cn/problem.php?pid=1901
题目大意:

给一个字符串。
问你,有多少个P的取值方案,可以对任意i,让s[i] == s[i+p] (i+p不超字符串范围)

并且最终方案额外加上一个输出 “总串长”。

就是求所以的公共前后缀。用Len-公共前后缀的长度就是答案。

公共前后缀参考我另外一篇博客:https://blog.csdn.net/qq_21433411/article/details/89576376

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>

#define LL long long
using namespace std;

char s[1000005];
int f[1000005];

void getVal(char P[], int l)
{
    int i = 0, j = -1;
    f[0] = -1;
    while (i < l){
        if (j == -1 || P[i] == P[j])  {
            i++;  j++;  f[i] = j;
        }
        else{
            j = f[j];
        }
    }
}

queue<int> q;
int main()
{
    int t, T=1;
    scanf("%d", &t);
    while(t--){
        scanf("%s", s);
        int Len=strlen(s);
        getVal(s, Len);
        int i=Len;
        while(i){
            i=f[i];
            q.push(Len-i);
        }
        printf("Case #%d: %d\n", T++, q.size());
        while(q.size()){
            printf("%d%c", q.front(), q.size()==1?'\n':' ');
            q.pop();
        }
    }

    return 0;
}