fork download
copy 
  1. // submitted by DeadlyPoison
  2. #include <bits/stdc++.h>
  3. #ifndef ONLINE_JUDGE
  4. #include "debug.h"
  5. #else
  6. #define debug(...) 42
  7. #endif
  8. using namespace std;
  9. typedef long long ll;
  10. typedef unsigned int uint;
  11. #define pii pair<int, int>
  12. #define pll pair<ll, ll>
  13. #define vi vector<int>
  14. #define vll vector<ll>
  15. #define vpii vector<pii>
  16. #define vpll vector<pll>
  17. #define mii map<int, int>
  18. #define mll map<ll, ll>
  19. #define all(v) ((v).begin()), ((v).end())
  20. #define allr(v) ((v).rbegin()), ((v).rend())
  21. #define f first
  22. #define s second
  23. #define pb push_back
  24. #define pf push_front
  25. #define el '\n'
  26. #define loop(i, ini, n) for (int i = ini; i < n; i++)
  27. #define loope(i, ini, n) for (int i = ini; i <= n; i++)
  28. #define loopdez(i, ini) for (int i = ini; i >= 0; i--)
  29. #define loopde(i, ini, n) for (int i = ini; i >= n; i--)
  30. #define loopd(i, ini, n) for (int i = ini; i > n; i--)
  31. #define sz(v) ((int)((v).size()))
  32. #define LOOP(n) for (int i = 0; i < n; i++)
  33. #define mx(v) *max_element(all(v))
  34. #define mn(v) *min_element(all(v))
  35. #define up(x) transform(all(x), x.begin(), ::toupper)
  36. #define down(x) transform(all(x), x.begin(), ::tolower)
  37. #define inf LLONG_MAX
  38.  
  39. //======================================================
  40.  
  41. //  freopen("input.in", "r", stdin);
  42. //  freopen("output.out", "w", stdout);
  43.  
  44. //======================================================
  45.  
  46. void fast()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50.     cout.tie(nullptr);
  51. }
  52.  
  53. //======================================================
  54. const ll N = 30000 + 5, base2 = 131, base1 = 127, mod1 = 1e9 + 7, mod2 = 2e9 + 11;
  55. ll pw1[N], pw2[N];
  56. ll powmod(ll x, ll y, ll m)
  57. {
  58.     ll res = 1;
  59.     x = x % m;
  60.     if (x == 0)
  61.         return 0;
  62.     while (y > 0)
  63.     {
  64.         if (y & 1)
  65.             res = (res * x) % m;
  66.         y = y >> 1;
  67.         x = (x * x) % m;
  68.     }
  69.     return res;
  70. }
  71. void init()
  72. {
  73.     pw1[0] = 1;
  74.     pw2[0] = 1;
  75.     for (int i = 1; i < N; i++)
  76.     {
  77.         pw1[i] = (1LL * pw1[i - 1] * base1) % mod1;
  78.         pw2[i] = (1LL * pw2[i - 1] * base2) % mod2;
  79.     }
  80. }
  81.  
  82. pair<ll, ll> pref[N];
  83.  
  84. pair<ll, ll> get(ll l, ll r, pair<ll, ll> pp[])
  85. {
  86.     auto ret = pp[r];
  87.     ll szz = r - l + 1;
  88.     l--;
  89.     if (l >= 0)
  90.     {
  91.         ret.f -= (pp[l].f * pw1[szz]) % mod1;
  92.  
  93.         ret.s -= (pp[l].s * pw2[szz]) % mod2;
  94.     }
  95.     if (ret.f < 0)
  96.         ret.f += mod1;
  97.     if (ret.s < 0)
  98.         ret.s += mod2;
  99.     return ret;
  100. }
  101. void Hash(string st, pair<ll, ll> p[])
  102. {
  103.     ll h1 = 0, h2 = 0;
  104.     LOOP(sz(st))
  105.     {
  106.         char dig = st[i];
  107.         h1 = ((h1 * base1) % mod1 + dig) % mod1;
  108.         h2 = ((h2 * base2) % mod2 + dig) % mod2;
  109.         p[i] = {h1, h2};
  110.     }
  111. }
  112. void solve()
  113. {
  114.     string st;
  115.     cin >> st;
  116.     int n = sz(st);
  117.     Hash(st, pref);
  118.     loop(i, 1, n)
  119.     {
  120.         auto h1 = pref[i - 1];
  121.         int cnt = 0;
  122.         int ps = n / i;
  123.         if (ps * i == n)
  124.             ps--;
  125.  
  126.         for (int j = i - 1; j < n - 1; j += i)
  127.         {
  128.             auto h2 = get(j - i + 1, j, pref);
  129.             if (h1 == h2)
  130.                 cnt++;
  131.         }
  132.         if (cnt == ps)
  133.         {
  134.             if (get(0, n % i - 1, pref) == get(n - n % i, n - 1, pref))
  135.                 cout
  136.                     << i << ' ';
  137.         }
  138.     }
  139.     cout << n << ' ';
  140.     cout << el;
  141. }
  142. int main()
  143. {
  144.     fast();
  145.     init();
  146.     int t = 1;
  147.     // cin >> t;
  148.     // int tt=t;
  149.     loope(i, 1, t)
  150.     {
  151.         solve();
  152.     }
  153.     return 0;
  154. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
aaaaaa
stdout
copy 
4 5 6
https://ideone.com/wCgmoL
language:
C++ (gcc 8.3)
created:
30 days ago
visibility:
public

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!