Stikked

双哈希模板

From Idiotic Leopard, 4 Years ago, written in Plain Text, viewed 326 times.
URL http://axuhongbo.top/paste/view/7110d783 Embed
Download Paste or View Raw
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. inline int add(int a, int b, int mod){
  5.   a+=b;
  6.   return a>=mod?a-mod:a;
  7. }
  8. inline int sub(int a, int b, int mod){
  9.   a-=b;
  10.   return a<0?a+mod:a;
  11. }
  12. inline int mul(LL a, int b, int mod){
  13.   a*=b;
  14.   return a>=mod?a%mod:a;
  15. }
  16. const int N=(1<<20);
  17. const int K=3;
  18. const int mods[K]={1000000007, 1000000009, 1010102101};
  19. const int _BS=13131;
  20. struct Int{
  21.   int vl[K];
  22.   Int(int v=0){
  23.     for(int i=0; i<K; i++)
  24.       vl[i]=v%mods[i];
  25.   }
  26.   Int operator+(const Int& he) const{
  27.     Int ret;
  28.     for(int i=0; i<K; i++)
  29.       ret.vl[i]=add(vl[i], he.vl[i], mods[i]);
  30.     return ret;
  31.   }
  32.   Int operator-(const Int& he) const{
  33.     Int ret;
  34.     for(int i=0; i<K; i++)
  35.       ret.vl[i]=sub(vl[i], he.vl[i], mods[i]);
  36.     return ret;
  37.   }
  38.   Int operator*(const Int& he) const{
  39.     Int ret;
  40.     for(int i=0; i<K; i++)
  41.       ret.vl[i]=mul(vl[i], he.vl[i], mods[i]);
  42.     return ret;
  43.   }
  44.   pair<LL,LL> to_pll() const{
  45.     return {vl[0]*(LL)mods[1]+vl[1], vl[2]};
  46.   }
  47. };
  48. char c[N];
  49. Int BS(_BS);
  50. map<pair<LL,LL>, int> id;
  51. vector<int> ans;
  52. vector<int> v[N];
  53. int main(){
  54.   scanf("%s", c);
  55.   int len=strlen(c);
  56.   Int dbs=Int(1);
  57.   for(int i=0; i<len; i++) dbs=dbs*BS;
  58.   Int cur;
  59.   for(int i=0; i<len+len-1; i++){
  60.     cur=cur*BS+Int(c[i%len]);
  61.     if(i-len>=0) cur=cur-dbs*Int(c[i-len]);
  62.     if(i>=len-1){
  63.       int idx=i-(len-1);
  64.       pair<LL,LL> p=cur.to_pll();
  65.       if(id.find(p) == id.end()){
  66.         ans.push_back(idx);
  67.         id[p]=idx;
  68.       }
  69.       v[id[p]].push_back(idx);
  70.     }
  71.   }
  72.   printf("%d\n", (int)ans.size());
  73.   for(int idx: ans){
  74.     printf("%d", (int)v[idx].size());
  75.     for(int i: v[idx]) printf(" %d", i);
  76.     puts("");
  77.   }
  78. }
  79.  

Reply to "双哈希模板"

Here you can reply to the paste above

captcha
Powered by Stikked