fork download
copy 
  1. #pragma GCC optimize("O3")
  2.  
  3. // RollingHash
  4. // https://w...content-available-to-author-only...c.net/problem/1605
  5. #include<bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. // https://q...content-available-to-author-only...a.com/recuraki/items/652f97f5330fde231ddb#%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E8%A1%9D%E7%AA%81%E6%94%BB%E6%92%83%E3%81%AE%E3%83%8F%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0%E3%81%8B%E3%82%89%E8%BA%AB%E3%82%92%E5%AE%88%E3%82%8B%E6%96%B9%E6%B3%95
  10. #include <chrono>
  11. struct custom_hash {
  12.     static uint64_t splitmix64(uint64_t x) {
  13.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  14.         x += 0x9e3779b97f4a7c15;
  15.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  16.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  17.         return x ^ (x >> 31);
  18.     }
  19.  
  20.     size_t operator()(uint64_t x) const {
  21.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  22.         return splitmix64(x + FIXED_RANDOM);
  23.     }
  24. };
  25.  
  26. // Safer-Faster-RollingHash
  27. // https://q...content-available-to-author-only...a.com/keymoon/items/11fac5627672a6d6a9f6
  28. // https://a...content-available-to-author-only...r.jp/contests/abc141/submissions/7717102
  29. typedef unsigned long long int ull;
  30.  
  31. #define MAXLEN 500005
  32.  
  33. const ull MASK30 = (1ull << 30) - 1;
  34. const ull MASK31 = (1ull << 31) - 1;
  35. const ull MOD = (1ull << 61) - 1;
  36. const ull MASK61 = MOD;
  37. const ull POSITIVIZER = MOD * 4;
  38.  
  39. //mod 2^61-1
  40. ull CalcMod(ull x)
  41. {
  42.     ull xu = x >> 61;
  43.     ull xd = x & MASK61;
  44.     ull res = xu + xd;
  45.     if (res >= MOD) res -= MOD;
  46.     return res;
  47. }
  48.  
  49. //a*b mod 2^61-1
  50. ull Mul(ull a, ull b)
  51. {
  52.     ull au = a >> 31;
  53.     ull ad = a & MASK31;
  54.     ull bu = b >> 31;
  55.     ull bd = b & MASK31;
  56.     ull mid = ad * bu + au * bd;
  57.     ull midu = mid >> 30;
  58.     ull midd = mid & MASK30;
  59.     return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
  60. }
  61.  
  62. ull hBase;
  63. vector<ull> powMemo;
  64. void genBase(mt19937_64 &eg){
  65.   hBase=0;
  66.   while(hBase==0){
  67.     hBase=CalcMod((ull)eg());
  68.   }
  69.  
  70.   powMemo.resize(MAXLEN);
  71.   powMemo[0]=1;
  72.   for(int i=1;i<MAXLEN;i++){
  73.     powMemo[i]=Mul(powMemo[i-1],hBase);
  74.   }
  75. }
  76.  
  77. vector<ull> genHash(string s){
  78.   vector<ull> res={0};
  79.   ull cur=0;
  80.   for(auto &nx : s){
  81.     cur=Mul(cur,hBase);
  82.     cur=CalcMod(cur+nx);
  83.     res.push_back(cur);
  84.   }
  85.   return res;
  86. }
  87.  
  88. // substr [l,r) (0-indexed)
  89. ull subHash(int l,int r,vector<ull> &hv){
  90.   return CalcMod(hv[r] + POSITIVIZER - Mul(hv[l], powMemo[r-l]));
  91. }
  92.  
  93. int main(){
  94.   random_device seed_gen;
  95.   mt19937_64 engine(seed_gen());
  96.  
  97.   genBase(engine);
  98.  
  99.   ios::sync_with_stdio(false);
  100.   cin.tie(nullptr);
  101.  
  102.   while(true){
  103.     string s;
  104.     cin >> s;
  105.     if(s[0]=='0'){break;}
  106.  
  107.     long long res=0;
  108.     int l=s.size();
  109.     vector<ull> hv=genHash(s);
  110.     for(int u=1;u<=(l/2);u++){
  111.       bool pre=false;
  112.       int f=(u-1);
  113.       while(f+u<l){
  114.         int s=(f+u);
  115.         int lef=1,rig=u;
  116.         while(lef<=rig){
  117.           int te=(lef+rig)/2;
  118.           if(subHash(f+1-te,f+1,hv)==subHash(s+1-te,s+1,hv)){lef=te+1;}
  119.           else{rig=te-1;}
  120.         }
  121.         if(rig==u){
  122.           // match
  123.           if(pre){res+=u;}
  124.           else{res++;}
  125.           pre=true;
  126.           f=s;
  127.         }
  128.         else{
  129.           if(pre){
  130.             int ulef=1,urig=u;
  131.             while(ulef<=urig){
  132.               int te=(ulef+urig)/2;
  133.               if(subHash(f+1-u,f+1+te-u,hv)==subHash(f+1,f+1+te,hv)){ulef=te+1;}
  134.               else{urig=te-1;}
  135.             }
  136.             res+=urig;
  137.           }
  138.           pre=false;
  139.           f=s-rig;
  140.         }
  141.       }
  142.       if(pre){
  143.         int ulef=1,urig=u;
  144.         while(ulef<=urig){
  145.           int te=(ulef+urig)/2;
  146.           if(f+1+te>l){urig=te-1; continue;}
  147.           if(subHash(f+1-u,f+1+te-u,hv)==subHash(f+1,f+1+te,hv)){ulef=te+1;}
  148.           else{urig=te-1;}
  149.         }
  150.         res+=urig;
  151.       }
  152.     }
  153.     cout << res << "\n";
  154.   }
  155. }
  156.  
Success #stdin #stdout 0.01s 6988KB
comments (?)
stdin
copy 
AGGA
AGAG
ATTCGATTCGATTCG
0
stdout
copy 
1
1
9
https://ideone.com/VXeNUf
language:
C++14 (gcc 8.3)
created:
161 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!