Advertisement
Ahmed_Negm

Untitled

May 20th, 2024
555
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.44 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define nl "\n"
  6.  
  7. void files(){
  8.     ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
  9.     #ifndef ONLINE_JUDGE
  10.         freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  11.     #endif
  12. }
  13.  
  14. struct Hash{
  15.     const static int mod = 1e9 + 7,p1 = 31,p2 = 37;
  16.     int n;
  17.     vector<int> h1,h2,pw1,pw2;
  18.     Hash(string &s){
  19.         n = s.size();
  20.         h1 = vector<int>(n + 1,0),h2 = vector<int>(n + 1,0);
  21.         pw1 = vector<int>(n + 1,1),pw2 = vector<int>(n + 1,1);
  22.         for(int i = 1; i <= n; i++){
  23.             h1[i] = (1LL * h1[i - 1] * p1 + s[i - 1]) % mod;
  24.             h2[i] = (1LL * h2[i - 1] * p2 + s[i - 1]) % mod;
  25.             pw1[i] = 1LL * pw1[i - 1] * p1 % mod;
  26.             pw2[i] = 1LL * pw2[i - 1] * p2 % mod;
  27.         }
  28.     }
  29.  
  30.     pair<int,int> get(int l,int r){
  31.         int a = (h1[r] - 1LL * h1[l - 1] * pw1[r - l + 1] % mod + mod) % mod;
  32.         int b = (h2[r] - 1LL * h2[l - 1] * pw2[r - l + 1] % mod + mod) % mod;
  33.         return {a,b};
  34.     }
  35. };
  36.  
  37.  
  38. void solve(){
  39.     int n; cin>>n;
  40.     string s; cin>>s;
  41.     string t = s;
  42.     reverse(t.begin(),t.end());
  43.     Hash h1(s),h2(t);
  44.  
  45.     int ans = 0;
  46.     int res = 1;
  47.     int l = 0, r = n;
  48.     while(l<=r){
  49.         int m = (l + r) / 2;
  50.         bool ok = false;
  51.         for(int i = m+1; i+m <= n and i-m>=1; i++){
  52.             int left = i-m,right = i+m;
  53.             auto a = h1.get(left,right);
  54.             auto b = h2.get(n-right+1,n-left+1);
  55.             if(a == b){
  56.                 ok = true;
  57.                 break;
  58.             }
  59.         }
  60.         if(ok){
  61.             ans = m;
  62.             res = max(res,2*ans+1);
  63.             l = m + 1;
  64.         }else r = m - 1;
  65.     }
  66.  
  67.  
  68.     l = 0, r = n, ans = 0;
  69.     while(l<=r){
  70.         int m = (l + r) / 2;
  71.         bool ok = false;
  72.         for(int i = m+1; i+m < n and i-m>=1; i++){
  73.             int left = i-m,right = i+m+1;
  74.             // cout<<left<<" "<<right<<' '<<m<<nl;
  75.             auto a = h1.get(left,right);
  76.             auto b = h2.get(n-right+1,n-left+1);
  77.             if(a == b){
  78.                 ok = true;
  79.                 break;
  80.             }
  81.         }
  82.         if(ok){
  83.             ans = m;
  84.             res = max(res,2*ans+2);
  85.             l = m + 1;
  86.         }else r = m - 1;
  87.     }
  88.  
  89.  
  90.     cout<<res<<nl;
  91.  
  92. }
  93.  
  94. int main(){
  95.     files();
  96.     int t = 1;
  97.     // cin>>t;
  98.     while(t--) solve();
  99.  
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement