ccbeginner

TIOJ 1515 (TLE...)

Oct 30th, 2020 (edited)
896
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define SZ(X) ((int)(X).size())
  5.  
  6. int modmul(int A, int B, int mod)
  7. {
  8.     return (A*B-(int)((long double)A*B/mod)*mod+mod)%mod;
  9. }
  10.  
  11. class Strhash{
  12.     private:
  13.         vector<long long> hash, pows;
  14.         const long long mod = 304250263527209;
  15.     public:
  16.         Strhash(string s, int prm=0xdefaced){
  17.             hash.emplace_back(0);
  18.             pows.emplace_back(1);
  19.             for(unsigned i = 0; i < s.size(); ++i){
  20.                 hash.emplace_back((hash.back()*prm+s[i])%mod);
  21.                 pows.emplace_back(pows.back()*prm%mod);
  22.             }
  23.         }
  24.         Strhash(char *c, int prm=0xdefaced){
  25.             hash.emplace_back(0);
  26.             pows.emplace_back(1);
  27.             for(int i = 0; c[i] != '\0'; ++i){
  28.                 hash.emplace_back((hash.back()*prm+c[i])%mod);
  29.                 pows.emplace_back(pows.back()*prm%mod);
  30.             }
  31.         }
  32.         long long gethash(int l, int r){//[l,r)
  33.             return (hash[r]+mod-modmul(hash[l], pows[r-l], mod))%mod;
  34.         }
  35. };
  36.  
  37. int same[200000];
  38.  
  39. int32_t main(){
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.     int small=1, big;
  43.     string s;
  44.     cin >> big >> s;
  45.     Strhash tool(s, 10079);
  46.     while(big >= small){
  47.         int cnt = 0;
  48.         int mid = (big + small) / 2;
  49.         for(int i = 0; i+mid <= SZ(s); ++i){
  50.             same[cnt++] = tool.gethash(i, i+mid);
  51.         }
  52.         sort(same, same+cnt);
  53.         if(unique(same, same+cnt)-same == cnt){
  54.             big = mid - 1;
  55.         }else{
  56.             small = mid + 1;
  57.         }
  58.         //cout << SZ(same ) << ' ' << mid << '\n';
  59.     }
  60.     cout << big << '\n';
  61.     return 0;
  62. }
RAW Paste Data