FZU 1901Period II(擴充kmp)

題意：

給你一個字元串，問你有多少個p，滿足s[i] == s[i+p]（i+p <= len)。

思路：

一開始往kmp想了，不斷遞歸循環節，但感覺不是很好搞，然後就想了一下exkmp，發現exkmp就是專門搞這種事的，因為算的是字尾和整個的公共部分，如果這個公共部分等于字尾的長度，那就滿足題目要求的條件，把（串的長度 - 字尾的長度）加入答案，最後排個序就可以了。 注意整個串的情況要特判一下，不然加入答案的就是0而不是整個串的長度。

吐槽一下編譯器的版本，交了好幾發CE，還不給為什麼CE，很氣。

/**
* Author : zzy
* Date : 2020-04-20-16.09.17 Monday
*/
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <iterator>
#include <list>
#include <cstdio>
#include <iomanip>

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 1000000+100;
int nxt[maxn], extend[maxn];
char x[maxn], y[maxn];
 int res[maxn];

void pre_EKMP(char x[], int m, int nxt[]) {
	nxt[0] = m;
	int j = 0;
	while (j + 1 < m && x[j] == x[j + 1]) ++j;
	nxt[1] = j;
	int k = 1;
	for (int i = 2; i < m; ++i) {
		int p = nxt[k] + k - 1;
		int L = nxt[i - k];
		if (i + L < p + 1) nxt[i] = L;
		else {
			j = max(0, p - i + 1);
			while (i + j < m && x[i + j] == x[j]) ++j;
			nxt[i] = j;
			k = i;
		}
	}
}

int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.precision(0);
//    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    int tc;
    cin >> tc;
    for (int k = 1; k <= tc; ++k) {
        cin >> x;
        int len = strlen(x);
        pre_EKMP(x, len, nxt);
        int now = 0;
        res[now++] = len;
        for (int i = len-1; i >= 1; --i) {
            int correct = len-1-i+1;
            if (nxt[i] == correct) res[now++] = len-correct;
        }
        sort(res, res+now);
        cout << "Case #" << k << ": " << now << '\n';
        for (int i = 0; i < now; ++i) {
            cout << res[i];
            if (i != now-1) cout << ' ';
        }
        cout << '\n';
    }

//#ifdef LOCAL_DEFINE
//    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
//#endif
    return 0;
}