Advertisement
Saleh127

Spoj LPS / Hashing

Jan 3rd, 2022
980
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-03-13.26.45
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll mod[2]= {1000007707,1000007909};
  13. ll base[2]= {149,307};
  14. ll hash1[2][1000007];
  15. ll hash2[2][1000007];
  16. ll p1[1000007];
  17. ll p2[1000007];
  18.  
  19. void pwr()
  20. {
  21.     p1[0]=p2[0]=1;
  22.  
  23.     for(ll i=1; i<=1000005; i++)
  24.     {
  25.         p1[i]=(p1[i-1]*base[0])%mod[0];
  26.         p2[i]=(p2[i-1]*base[1])%mod[1];
  27.     }
  28. }
  29.  
  30. void hashing(string a,string b)
  31. {
  32.     ///for string a
  33.  
  34.     hash1[0][0]=hash1[1][0]=0;
  35.  
  36.     for(ll i=1; i<=a.size(); i++)
  37.     {
  38.         hash1[0][i]=(hash1[0][i-1]*base[0] + a[i-1])%mod[0];
  39.         hash1[1][i]=(hash1[1][i-1]*base[1] + a[i-1])%mod[1];
  40.     }
  41.  
  42.     ///for string b
  43.  
  44.     hash2[0][0]=hash2[1][0]=0;
  45.  
  46.     for(ll i=b.size(); i>=1; i--)
  47.     {
  48.         hash2[0][i]=(hash2[0][i+1]*base[0] + b[i-1])%mod[0];
  49.         hash2[1][i]=(hash2[1][i+1]*base[1] + b[i-1])%mod[1];
  50.     }
  51.  
  52. }
  53.  
  54. ll forwardhash(ll l,ll r)
  55. {
  56.     ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];
  57.  
  58.     if(x<0) x+=mod[0];
  59.  
  60.     return x;
  61. }
  62.  
  63. ll backwardhash(ll l,ll r)
  64. {
  65.     ll x=(hash2[0][l] - hash2[0][r+1]*p1[r-l+1])%mod[0];
  66.  
  67.     if(x<0) x+=mod[0];
  68.  
  69.     return x;
  70. }
  71.  
  72.  
  73. bool check(ll mid,ll n)
  74. {
  75.     ll x,y;
  76.  
  77.     for(ll i=1; i<=n-mid+1; i++)
  78.     {
  79.         x=forwardhash(i,i+mid-1);
  80.         y=backwardhash(i,i+mid-1);
  81.  
  82.        // cout<<x<<" "<<y<<" "<<mid<<nl;
  83.  
  84.         if(x==y)
  85.         {
  86.             return 1;
  87.         }
  88.     }
  89.  
  90.     return 0;
  91. }
  92.  
  93. int main()
  94. {
  95.     ios_base::sync_with_stdio(0);
  96.     cin.tie(0);
  97.     cout.tie(0);
  98.  
  99.     pwr();
  100.  
  101.  
  102.     ll sz;
  103.  
  104.     string a,b;
  105.  
  106.     cin>>sz;
  107.  
  108.     cin>>a;
  109.  
  110.     b=a;
  111.  
  112.     hashing(a,b);
  113.  
  114.     ll l=1,h=sz,ans=0;
  115.  
  116.     while(l<=h)
  117.     {
  118.         ll mid=(l+h)/2;
  119.         ll ee=0;
  120.  
  121.         if(check(mid,sz))
  122.         {
  123.             ans=max(mid,ans);
  124.             ee=1;
  125.             l=mid+1;
  126.         }
  127.         if(mid+1<=sz && check(mid+1,sz))
  128.         {
  129.             ans=max(mid+1,ans);
  130.             ee=1;
  131.             l=mid+2;
  132.         }
  133.         if(ee==0)
  134.         {
  135.             h=mid-1;
  136.         }
  137.     }
  138.  
  139.     cout<<ans<<nl;
  140.  
  141.     get_lost_idiot;
  142. }
  143.  
  144.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement