fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mod = 998244353;
  5. const int base = 311;
  6. const int N = 100100;
  7.  
  8. struct minSegtree {
  9.  
  10.     vector<int> t;
  11.  
  12.     minSegtree (int sz = 0){
  13.         t = vector<int>(sz * 4, N);
  14.     }
  15.  
  16.     void upd (int id, int l, int r, int k){
  17.         if (l == r){
  18.             t[id] = k;
  19.             return;
  20.         }
  21.         int m = l + r >> 1;
  22.         if (k <= m){
  23.             upd(id * 2, l, m, k);
  24.         } else {
  25.             upd(id * 2 + 1, m + 1, r, k);
  26.         }
  27.         t[id] = min(t[id * 2], t[id * 2 + 1]);
  28.         return;
  29.     }
  30.  
  31.     int get (int id, int l, int r, int u, int v){
  32.         if (l > v || r < u){
  33.             return N;
  34.         }
  35.         if (l >= u && r <= v){
  36.             return t[id];
  37.         }
  38.         int m = l + r >> 1;
  39.         return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
  40.     }
  41.  
  42. };
  43.  
  44. struct maxSegtree {
  45.  
  46.     vector<int> t;
  47.  
  48.     maxSegtree (int sz = 0){
  49.         t = vector<int>(sz * 4, 0);
  50.     }
  51.  
  52.     void upd (int id, int l, int r, int k){
  53.         if (l == r){
  54.             t[id] = k;
  55.             return;
  56.         }
  57.         int m = l + r >> 1;
  58.         if (k <= m){
  59.             upd(id * 2, l, m, k);
  60.         } else {
  61.             upd(id * 2 + 1, m + 1, r, k);
  62.         }
  63.         t[id] = max(t[id * 2], t[id * 2 + 1]);
  64.         return;
  65.     }
  66.  
  67.     int get (int id, int l, int r, int u, int v){
  68.         if (l > v || r < u){
  69.             return 0;
  70.         }
  71.         if (l >= u && r <= v){
  72.             return t[id];
  73.         }
  74.         int m = l + r >> 1;
  75.         return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
  76.     }
  77.  
  78. };
  79.  
  80. int add (int a, int b){
  81.     a += b;
  82.     if (a >= mod){
  83.         a -= mod;
  84.     }
  85.     return a;
  86. }
  87.  
  88. int sub (int a, int b){
  89.     a -= b;
  90.     if (a < 0){
  91.         a += mod;
  92.     }
  93.     return a;
  94. }
  95.  
  96. int mul (int a, int b){
  97.     return 1ll * a * b % mod;
  98. }
  99.  
  100. int n, pw[N], lhs[N], rhs[N], f[N], tl[N * 4], tr[N * 4], ans = 0, cnt = 0;
  101. vector<int> pos;
  102. string s;
  103. minSegtree mino, mine;
  104. maxSegtree maxo, maxe;
  105.  
  106. bool palindrome (int l, int r){
  107.     int L = sub(lhs[r], mul(lhs[l - 1], pw[r - l + 1]));
  108.     int R = sub(rhs[l], mul(rhs[r + 1], pw[r - l + 1]));
  109.     return (L == R);
  110. }
  111.  
  112. void init (){
  113.     mino = mine = minSegtree(n + 7);
  114.     maxo = maxe = maxSegtree(n + 7);
  115.     sort(pos.begin(), pos.end(), [&](int i, int j){
  116.         return (f[i] > f[j]);
  117.     });
  118. }
  119.  
  120. bool checkeq (int mid1, int mid2){
  121.     int l = mid1 - (mid2 - mid1 - 1) / 2;
  122.     int r = mid2 + (mid2 - mid1) / 2;
  123.     return palindrome(l, r);
  124. }
  125.  
  126. int32_t main (){
  127.     ios::sync_with_stdio(false); cin.tie(nullptr);
  128.     const string task = "padble";
  129.     freopen ((task + ".inp").c_str(), "r", stdin);
  130.     freopen ((task + ".out").c_str(), "w", stdout);
  131.     cin >> s;
  132.     n = s.size();
  133.     s = '&' + s;
  134.     pw[0] = 1;
  135.     for (int i = 1; i < N; ++i){
  136.         pw[i] = mul(pw[i - 1], base);
  137.     }
  138.     lhs[0] = rhs[n + 1] = 0;
  139.     for (int i = 1; i <= n; ++i){
  140.         pos.push_back(i);
  141.         lhs[i] = add(mul(lhs[i - 1], base), (int)(s[i]));
  142.     }
  143.     for (int i = n; i >= 1; --i){
  144.         rhs[i] = add(mul(rhs[i + 1], base), (int)(s[i]));
  145.     }
  146.     for (int i = 1; i <= n; ++i){
  147.         int l = 1, r = min(i - 1, n - i);
  148.         f[i] = 0;
  149.         while (l <= r){
  150.             int m = l + r >> 1;
  151.             if (palindrome(i - m, i + m)){
  152.                 f[i] = m;
  153.                 l = m + 1;
  154.             } else {
  155.                 r = m - 1;
  156.             }
  157.         }
  158.     }
  159.     init();
  160.     for (int &p : pos){
  161.         int l = max(1, p - 2 * f[p] - 1);
  162.         int r = min(n, p + 2 * f[p] + 1);
  163.         if (p & 1){
  164.             int L = mine.get(1, 1, n, l, p);
  165.             int R = maxe.get(1, 1, n, p, r);
  166.             if (!checkeq(L, p)){
  167.                 ans = max(ans, 2 * (p - L));
  168.             }
  169.             if (!checkeq(p, R)){
  170.                 ans = max(ans, 2 * (R - p));
  171.             }
  172.             mino.upd(1, 1, n, p);
  173.             maxo.upd(1, 1, n, p);
  174.         } else {
  175.             int L = mino.get(1, 1, n, l, p);
  176.             int R = maxo.get(1, 1, n, p, r);
  177.             if (!checkeq(L, p)){
  178.                 ans = max(ans, 2 * (p - L));
  179.             }
  180.             if (!checkeq(p, R)){
  181.                 ans = max(ans, 2 * (R - p));
  182.             }
  183.             mine.upd(1, 1, n, p);
  184.             maxe.upd(1, 1, n, p);
  185.         }
  186.     }
  187.     for (int i = 1; i <= n; ++i){
  188.         int l = 1, r = min(i, n - i);
  189.         f[i] = 0;
  190.         while (l <= r){
  191.             int m = l + r >> 1;
  192.             if (palindrome(i - m + 1, i + m)){
  193.                 f[i] = m;
  194.                 l = m + 1;
  195.             } else {
  196.                 r = m - 1;
  197.             }
  198.         }
  199.     }
  200.     init();
  201.     for (int &p : pos){
  202.         if (f[p] == 0){
  203.             continue;
  204.         }
  205.         int l = max(1, p - 2 * f[p]);
  206.         int r = min(n, p + 2 * f[p]);
  207.         if (p & 1){
  208.             int L = mino.get(1, 1, n, l, p);
  209.             int R = maxo.get(1, 1, n, p, r);
  210.             if (!checkeq(L, p)){
  211.                 ans = max(ans, 2 * (p - L));
  212.             }
  213.             if (!checkeq(p, R)){
  214.                 ans = max(ans, 2 * (R - p));
  215.             }
  216.             mino.upd(1, 1, n, p);
  217.             maxo.upd(1, 1, n, p);
  218.         } else {
  219.             int L = mine.get(1, 1, n, l, p);
  220.             int R = maxe.get(1, 1, n, p, r);
  221.             if (!checkeq(L, p)){
  222.                 ans = max(ans, 2 * (p - L));
  223.             }
  224.             if (!checkeq(p, R)){
  225.                 ans = max(ans, 2 * (R - p));
  226.             }
  227.             mine.upd(1, 1, n, p);
  228.             maxe.upd(1, 1, n, p);
  229.         }
  230.     }
  231.     if (ans == 0){
  232.         cout << -1;
  233.         return 0;
  234.     }
  235.     for (int i = 1; i <= n - ans + 1; ++i){
  236.         if (palindrome(i, i + ans / 2 - 1) && palindrome(i + ans / 2, i + ans - 1) && !palindrome(i, i + ans - 1)){
  237.             ++cnt;
  238.         }
  239.     }
  240.     if (cnt == 0 || ans == 0){
  241.         cout << -1;
  242.         return 0;
  243.     }
  244.     cout << ans << " " << cnt;
  245. }
  246.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BVpCtR
language:
C++14 (gcc 8.3)
created:
1 day 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!