字符串哈希。
不难发现, 该题题意为:
对于字符串s, 求出最短的字符串a满足: s由若干个a以及一个任意长度的a的前缀拼接而成。
#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 find (string s) {
int n = (int) s.size();
auto hs = HashString(s);
for (int i = 1; i <= n; i++) {
auto v = hs.get(0, i-1);
int j = i, flag = 1;
for (; j + i - 1 < n; j += i) {
if (! (v == hs.get(j, j + i - 1))) {
flag = 0;
break;
}
}
if (flag && (j == n || hs.get(j, n - 1) == hs.get(0, n - j - 1))) {
return i;
}
}
}
int main () {
string s;
while (cin >> s) {
cout << find(s) << endl;
}
return 0;
}