1 条题解
-
0
#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) { if (s == ".") break; int n = s.length(); s = "^" + s + "$"; initHash(n); int ans = -1; int i; // 循环节长度 len: 1~sqrt(n) for (i = 1; i * i <= n; i++) { if (n % i != 0) continue; int len = i; if (getHash(1, n - len) == getHash(len + 1, n)) { ans = n / len; break; } } if (ans != -1) { cout << ans << "\n"; continue; } // len: sqrt(n)~n for (; i >= 1; i--) { if (n % i != 0) continue; int len = n / i; if (getHash(1, n - len) == getHash(len + 1, n)) { ans = n / len; break; } } cout << ans << "\n"; } return 0; }
- 1
信息
- ID
- 677
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 69
- 已通过
- 20
- 上传者