这题实际上描述的就是后面要学习的 kmp 算法的一个概念。

但因为只要求整个字符串的，所以简单很多。

如果纯暴力，那么会是这么一个框架：

        for (int i = 1; i <= n; i++)
            if (s.substr(1, i) == s.substr(n - i + 1, i))
                cout << i << " ";

这样的做法能拿到 40 分（超时）。

那么显然可以使用哈希来加速下面的判断相等的语句，完成满分代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
string s;
// Hash
const long long MOD = 1000000007;
const int P = 29;
long long myHash[MAXN + 5];
long long powP[MAXN + 5];
// 初始化 s[1]~s[n] 的哈希
void initHash(int n)
{
    powP[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        myHash[i] = (myHash[i - 1] * P + s[i] - 'a' + 1) % MOD;
        powP[i] = powP[i - 1] * P % MOD;
    }
    powP[n + 1] = powP[n] * P % MOD;
}
// 获取 s[l]~s[r] 的哈希值
int getHash(int l, int r)
{
    return (myHash[r] - myHash[l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> s)
    {
        int n = s.length();
        s = "^" + s + "$";
        initHash(n);
        for (int i = 1; i <= n; i++)
            if (getHash(1, i) == getHash(n - i + 1, n))
                cout << i << " ";
        cout << "\n";
    }
    return 0;
}