fork download 
  1. #include "bits/stdc++.h"
  2. #define task "Tank"
  3. #define endl '\n'
  4. #define F first
  5. #define S second
  6. #define all(v) (v).begin(),(v).end()
  7.  
  8. using namespace std;
  9. using ll = long long;
  10. using pii = pair <int, int>;
  11. using vi = vector <ll>;
  12.  
  13. bool maxi(auto &u, auto v)
  14. {
  15.     if (u >= v) return 0;
  16.     return u = v, true;
  17. }
  18.  
  19. bool mini(auto &u, auto v)
  20. {
  21.     if (u <= v) return 0;
  22.     return u = v, true;
  23. }
  24.  
  25. const int MOD = 1e9 + 7;
  26. const int base = 311;
  27. const int N = 1e6 + 6;
  28. int n, k;
  29. string s;
  30. vi HashA, HashB, Pow;
  31.  
  32. ll Get1(int l, int r)
  33. {
  34.     return (HashA[r] - 1ll * HashA[l - 1] * Pow[r - l + 1] + 1ll * MOD * MOD) % MOD;
  35. }
  36.  
  37. ll Get2(int l, int r)
  38. {
  39.     return (HashB[l] - 1ll * HashB[r + 1] * Pow[r - l + 1] + 1ll * MOD * MOD) % MOD;
  40. }
  41.  
  42. void Solve()
  43. {
  44.     string t = s;
  45.     n *= k;
  46.     for (int i = 1; i < k; ++i)
  47.         s += t;
  48.  
  49.     HashA.assign(n + 2, 0);
  50.     HashB.assign(n + 2, 0);
  51.     Pow.assign(n + 2, 0);
  52.     Pow[0] = 1;
  53.     s = ' ' + s;
  54.     for (int i = 1; i <= n; ++i)
  55.     {
  56.         Pow[i] = 1ll * Pow[i - 1] * base % MOD;
  57.         HashA[i] = (1ll * HashA[i - 1] * base + s[i]) % MOD;
  58.     }
  59.     for (int i = n; i >= 1; --i)
  60.         HashB[i] = (1ll * HashB[i + 1] * base + s[i]) % MOD;
  61.  
  62.     int ans = 1;
  63.  
  64.     /// Le
  65.     for (int i = 1; i <= n; ++i)
  66.     {
  67.         int l = 1, r = min(i - 1, n - i);
  68.         while (l <= r)
  69.         {
  70.             int mid = l + r >> 1;
  71.             if (Get1(i, i + mid) == Get2(i - mid, i))
  72.                 maxi(ans, 2 * mid + 1), l = mid + 1;
  73.             else r = mid - 1;
  74.         }
  75.     }
  76.  
  77.     /// Chan
  78.     for (int i = 1; i <= n - 1; ++i)
  79.     {
  80.         int l = 1, r = min(i, n - i);
  81.         while (l <= r)
  82.         {
  83.             int mid = l + r >> 1;
  84.             if (Get1(i + 1, i + mid) == Get2(i - mid + 1, i))
  85.                 maxi(ans, 2 * mid), l = mid + 1;
  86.             else r = mid - 1;
  87.         }
  88.     }
  89.  
  90.     cout << ans;
  91. }
  92.  
  93. signed main()
  94. {
  95.     if (fopen(task".inp", "r"))
  96.     {
  97.         freopen(task".inp", "r", stdin);
  98.         freopen(task".out", "w", stdout);
  99.     }
  100.     ios_base::sync_with_stdio(0);
  101.     cin.tie(0), cout.tie(0);
  102.  
  103.     cin >> n >> k >> s;
  104.  
  105.     Solve();
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/oMxp2x
language:
C++14 (gcc 8.3)
created:
2 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!