Advertisement
nguyentien281006

paliny

Jan 28th, 2023
944
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const char DUMMY = '#';
  5.  
  6. int manacher(string s) {
  7.  
  8.  
  9.     int n = s.size() * 2 - 1;
  10.     vector <int> f = vector <int>(n, 0);
  11.  
  12.     string a = string(n, DUMMY);
  13.     for (int i = 0; i < n; i += 2) a[i] = s[i / 2];
  14.  
  15.     int l = 0, r = -1, cen, res = 0;
  16.     for (int i = 0, j = 0; i < n; i++) {
  17.         j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;
  18.         while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;
  19.         f[i] = --j;
  20.         if (i + j > r) {
  21.             r = i + j;
  22.             l = i - j;
  23.         }
  24.  
  25.         int len = (f[i] + i % 2) / 2 * 2 + 1 - i % 2;
  26.         if (len > res) {
  27.             res = len;
  28.             cen = i;
  29.         }
  30.     }
  31.     //in ra xau con dai nhat
  32.     //cout << cen << "\n" << res << "\n";
  33.     //if(cen % 2 == 0) cout << s.substr( cen / 2 - res/2, res) << "\n";
  34.     //else cout << s.substr( (cen+1)/2 - res/2, res);
  35.     return res;
  36. }
  37.  
  38. signed main(){
  39.     int c; cin >> c;
  40.     string s; cin >> s;
  41.     court << manacher(s);
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement