fork download
copy 
  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 <int>;
  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 N = 1e6 + 6;
  26. int n, k;
  27. string s;
  28.  
  29. void Solve()
  30. {
  31.     int dp[n][2] = {0};
  32.     int x1 = 0, y1 = -1;
  33.     int x2 = 0, y2 = -1;
  34.     int mx = 0, ans = 0;
  35.     for (int i = 0; i < n; i++)
  36.     {
  37.         int k = 0;
  38.         if (i > y1) k = 1;
  39.         else k = min(dp[x1 + y1 - i][0], y1 - i + 1);
  40.         while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;
  41.         dp[i][0] = k--;
  42.         if (i + k > y1) x1 = i - k, y1 = i + k;
  43.         if (2 * dp[i][0] - 1 > mx) ans = i - k, mx = 2 * dp[i][0] - 1;
  44.         k = 0;
  45.         if (i <= y2) k = min(dp[x2 + y2 - i + 1][1], y2 - i + 1);
  46.         while(0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++;
  47.         dp[i][1] = k--;
  48.         if (i + k > y2) x2 = i - k - 1, y2 = i + k;
  49.         if (2 * dp[i][1] > mx) ans = i - k - 1, mx = 2 * dp[i][1];
  50.     }
  51.     cout << mx;
  52. }
  53.  
  54. signed main()
  55. {
  56.     if (fopen(task".inp", "r"))
  57.     {
  58.         freopen(task".inp", "r", stdin);
  59.         freopen(task".out", "w", stdout);
  60.     }
  61.     ios_base::sync_with_stdio(0);
  62.     cin.tie(0), cout.tie(0);
  63.  
  64.     cin >> n >> k >> s;
  65.     string t = s;
  66.     n *= k;
  67.     for (int i = 1; i < k; ++i)
  68.         s += t;
  69.     ///cout << s;
  70.  
  71.     Solve();
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2kDsaE
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!