fork(1) download
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. // Warning: Change mod and N according to question
  8. const int mod = (1LL << 31)-1;
  9. const int N = 1e6 + 3;
  10.  
  11. #define int long long
  12. #define MP make_pair
  13. #define F first
  14. #define S second
  15. #define sz(s) ((int)s.size())
  16.  
  17. int rand(int l, int r){
  18. static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  19. std::uniform_int_distribution<int> ludo(l, r); return ludo(rng);
  20. }
  21.  
  22. inline int add(int x, int y, int mod = ::mod) {
  23. x += y;
  24. if (x >= mod or x < 0) x %= mod;
  25. if (x >= 0) return x;
  26. return x + mod;
  27. }
  28. inline int mul(int x, int y, int mod = ::mod) {
  29. if (x >= mod or x + mod < 0) x %= mod;
  30. if (y >= mod or y + mod < 0) y %= mod;
  31. x *= y;
  32. if (x >= mod or x + mod < 0) x %= mod;
  33. if (x >= 0) return x;
  34. return x + mod;
  35. }
  36. inline int sub(int x, int y, int mod = ::mod) {
  37. x -= y;
  38. if (x + mod < 0 or x >= mod) {
  39. x %= mod;
  40. }
  41. if (x >= 0) return x;
  42. return x + mod;
  43. }
  44.  
  45. char s[N];
  46.  
  47. struct Hash {
  48. vector<pair<int,int>> H, pre;
  49. Hash(const char *s, int N, int b1 = 41, int b2 = 53) :
  50. H(N + 5), pre(N + 5) {
  51. pre[0].F = 1, b1 = rand(37, 1 << 10);
  52. pre[0].S = 1, b2 = rand(41, 1 << 9);
  53. int cur1 = 0, cur2 = 0;
  54. for (int i = 1; i <= N; ++i) {
  55. pre[i].F = mul(pre[i-1].F, b1);
  56. pre[i].S = mul(pre[i-1].S, b2);
  57. cur1 = add(mul(cur1, b1), (s[i] - 'a' + 1));
  58. cur2 = add(mul(cur2, b2), (s[i] - 'a' + 1));
  59. H[i].F = cur1, H[i].S = cur2;
  60. }
  61. }
  62. pair<int,int> get_hash(int l, int r) {
  63. int rem1 = mul(pre[r-l+1].F, H[l-1].F);
  64. int rem2 = mul(pre[r-l+1].S, H[l-1].S);
  65. return MP(sub(H[r].F, rem1), sub(H[r].S, rem2));
  66. }
  67. };
  68.  
  69.  
  70. signed main() {
  71. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  72. cin >> (s + 1);
  73. int n = strlen(s + 1);
  74. Hash ins(s, n);
  75. vector<int> answer;
  76. answer.reserve(n);
  77. for (int len = 1; len <= n; ++len) {
  78. bool pos = true;
  79. auto forLen = ins.get_hash(1, len);
  80. for (int i = len + len; i <= n && pos; i += len) {
  81. pos &= (forLen == ins.get_hash(i - len + 1, i));
  82. }
  83. int l = n / len * len;
  84. if (l != n) {
  85. int rem = n - l;
  86. pos &= ins.get_hash(1, rem) == ins.get_hash(l + 1, n);
  87. }
  88. if (pos) answer.push_back(len);
  89. }
  90. for (int x: answer) cout << x << ' ';
  91. return 0;
  92. }
Success #stdin #stdout 0s 4420KB
stdin
abbaba
stdout
5 6