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

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!