字符串哈希板子。
#include <bits/stdc++.h>
using namespace std;
class HashString {
private:
typedef unsigned long long ull;
const int P = 131;
vector<ull> p;
vector<ull> prefix;
int n;
public:
HashString(string s) {
n = s.size();
s.insert(0, "0");
p.resize(n + 1), p[0] = 1;
prefix.resize(n + 1, 0);
for(int i=1; i<=n; i++) {
p[i] = p[i-1] * P;
prefix[i] = prefix[i - 1] * P + s[i];
}
}
ull get(int l, int r) {
l++, r++;
return prefix[r] - prefix[l - 1] * p[r - l + 1];
}
};
int main () {
string s;
while (cin >> s) {
int n = (int) s.size();
auto hs = HashString(s);
for (int i = 1; i <= n; i ++) {
if (hs.get(0, i - 1) == hs.get(n - i, n - 1)) {
cout << i << " ";
}
}
cout << endl;
}
return 0;
}