fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  3. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  4. #define pub push_back
  5. #define pii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define int long long
  9. using namespace std;
  10.  
  11. const int N = 3e5 + 2;
  12. const int M = 350;
  13. const int mod1 = 1e9 + 7;
  14. const int mod2 = 2e9 + 11;
  15. const int LOG = 19;
  16. const long long inf = 3e18;
  17.  
  18. string s, t;
  19. int n;
  20. pii base[N], f1[N], f2[N];
  21. int prefix[N];
  22.  
  23. int minusMod(int a, int b, int mod) {
  24.     return ((a % mod) - (b % mod) + mod) % mod;
  25. }
  26. int mulMod(int a, int b, int mod) {
  27.     return ((a % mod) * (b % mod)) % mod;
  28. }
  29. void calBase() {
  30.     base[0].fi = 1;
  31.     base[0].se = 1;
  32.     FOR(i, 1, n, 1) {
  33.         base[i].fi = (base[i - 1].fi * 256) % mod1;
  34.         base[i].se = (base[i - 1].se * 256) % mod2;
  35.     }
  36. }
  37. void hashing(int o, string s, pii *f) {
  38.     if (o == 1) {
  39.         FOR(i, 1, n, 1) {
  40.             f[i].fi = (f[i - 1].fi * 256 + s[i]) % mod1;
  41.             f[i].se = (f[i - 1].se * 256 + s[i]) % mod2;
  42.         }
  43.     }
  44.     if (o == 2) {
  45.         FOD(i, n, 1, 1) {
  46.             f[i].fi = (f[i + 1].fi * 256 + s[i]) % mod1;
  47.             f[i].se = (f[i + 1].se * 256 + s[i]) % mod2;
  48.         }
  49.     }
  50. }
  51. pii getHash(int o, int l, int r, pii *f) {
  52.     if (o == 1) {
  53.         int x = minusMod(f[r].fi, mulMod(f[l - 1].fi, base[r - l + 1].fi, mod1), mod1);
  54.         int y = minusMod(f[r].se, mulMod(f[l - 1].se, base[r - l + 1].se, mod2), mod2);
  55.         return {x, y};
  56.     }
  57.     if (o == 2) {
  58.         int x = minusMod(f[l].fi, mulMod(f[r + 1].fi, base[r - l + 1].fi, mod1), mod1);
  59.         int y = minusMod(f[l].se, mulMod(f[r + 1].se, base[r - l + 1].se, mod2), mod2);
  60.         return {x, y};
  61.     }
  62. }
  63. void input() {
  64.     cin >> s;
  65.     n = s.size(); s = ' ' + s;
  66.     calBase();
  67.     hashing(1, s, f1);
  68.     hashing(2, s, f2);
  69. }
  70. int check(int l, int r) {
  71.     if (l == r) return 1;
  72.     int len = r - l + 1;
  73.     if (len % 2 == 1) {
  74.         int mid = (l + r) / 2;
  75.         pii hash_1 = getHash(1, l, mid, f1);
  76.         pii hash_2 = getHash(2, mid, r, f2);
  77.         if (hash_1 == hash_2) {
  78.             return check(l, mid - 1) + 1;
  79.         }
  80.     }
  81.     if (len % 2 == 0) {
  82.         int mid = (l + r) / 2;
  83.         pii hash_1 = getHash(1, l, mid, f1);
  84.         pii hash_2 = getHash(2, mid + 1, r, f2);
  85.         if (hash_1 == hash_2) {
  86.             return check(l, mid) + 1;
  87.         }
  88.     }
  89.     return 0;
  90. }
  91. void solve() {
  92.     input();
  93.     FOR(i, 1, n, 1) FOR(j, i, n, 1) {
  94.         int l = i;
  95.         int r = j;
  96.         int len = r - l + 1;
  97.  
  98.         int x = check(l, r);
  99.         if (x == 0) continue;
  100. //        cout << x << " " << l << " " << r << '\n';
  101.         prefix[1] ++;
  102.         prefix[x + 1] --;
  103.     }
  104.     FOR(i, 1, n, 1) {
  105.         prefix[i] = prefix[i - 1] + prefix[i];
  106.     }
  107.     FOR(i, 1, n, 1) {
  108.         cout << prefix[i] << " ";
  109.     }
  110. }
  111. signed main() {
  112.     #define name "baitap"
  113.     if (ifstream(name".inp")) {
  114.         freopen(name".inp", "r", stdin);
  115.         freopen(name".out", "w", stdout);
  116.     }
  117.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  118.     solve();
  119. }
  120.  
Success #stdin #stdout 0.01s 5592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5DISXK
language:
C++ (gcc 8.3)
created:
6 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!