fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define mod 1000000009LL
  5. #define base 257
  6. struct hashed_string{
  7.     private:
  8.     string s; ll n;
  9.     vector <ll> prefix;
  10.     vector <ll> pow;
  11.     public:
  12.     hashed_string(string a){
  13.         s = a; n = a.size();
  14.         prefix.assign(n, 0);
  15.         ll sum = 0;
  16.         pow.assign(n+1, 0);
  17.         pow[0] = 1;
  18.         for (int i = 1; i <= n; i++){
  19.             pow[i] = (pow[i-1] * base) % mod;
  20.         }
  21.         for (int i = 0; i < n; i++){
  22.             prefix[i] = ((sum * base) % mod + s[i] - 'a') % mod;
  23.             sum = prefix[i];
  24.         }
  25.     }
  26.     ll get_hash(ll l, ll r){
  27.         ll x = prefix[r];
  28.         if (l >= 1){
  29.             l--;
  30.             x = ((x - prefix[l] * pow[r - l] % mod) % mod + mod) % mod;
  31.         }
  32.         return x;
  33.     }
  34. };
  35. void solve(){
  36.     string s;
  37.     cin >> s;
  38.     ll n = s.size();
  39.     vector <ll> answ;
  40.     hashed_string v(s);
  41.     for (int i = 0; i < n; i++){
  42.         ll cur = v.get_hash(0, i);
  43.         ll sz = i + 1;
  44.         bool flag = true;
  45.         for (int j = 0; j + sz - 1 < n; j+=sz){
  46.             if (!(cur == v.get_hash(j, j + sz - 1))){
  47.                 flag = false;
  48.                 break;
  49.             }
  50.         }
  51.         if (n % sz >= 1){
  52.             ll left_over = n % sz;
  53.             flag = flag && (v.get_hash(n - left_over, n-1) == v.get_hash(0, left_over - 1));
  54.         }
  55.         if (flag) answ.push_back(sz);
  56.     }
  57.     for (auto &p : answ){
  58.         cout << p << " ";
  59.     }
  60. }
  61. int main(){
  62.     ios::sync_with_stdio(false);
  63.     cin.tie(nullptr);
  64.     solve();
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fU6YsJ
language:
C++14 (clang 8.0)
created:
2 hours 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!