fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define len 9
  6. #define mod 1000000007
  7. //#define mod 101
  8. int base=10;
  9. int power[len];
  10.  
  11. void init()
  12. {
  13.     power[0]=1;
  14.     for(int i=1;i<len;i++)
  15.     {
  16.         power[i]=(power[i-1]*base)%mod;
  17.     }
  18. }
  19.  
  20. int getindex(char ch)
  21. {
  22.     return ch-'0';
  23. }
  24.  
  25. void prefixHash(string s,vector<int> &ph)
  26. {
  27.     int n=ph.size();
  28.     ph[0]=getindex(s[0]);
  29.     for(int i=1;i<n;i++)
  30.     {
  31.         ph[i]=(((ph[i-1]*base)%mod)+getindex(s[i]))%mod;
  32.     }
  33. }
  34.  
  35. int calcHash(int l,int r,vector<int> &ph)
  36. {
  37.     if(l==0) return ph[r];
  38.     return (ph[r]-((ph[l-1]*power[r-l+1])%mod))%mod;
  39. }
  40.  
  41. int main()
  42. {
  43.     init();
  44.     //string s="123456";
  45.     string txt="22212121333333333333333333333333";
  46.     string pat="121";
  47.     int n=txt.size(),m=pat.size();
  48.  
  49.     vector<int> ph1(n),ph2(m);
  50.     prefixHash(txt,ph1);
  51.     prefixHash(pat,ph2);
  52.  
  53.  
  54.     for(int i=0;i+m<=n;i++) /// i,i+1,...,i+m-1
  55.     {
  56.         int x=calcHash(i,i+m-1,ph1); /// txt[i to t+m-1]
  57.         int y=calcHash(0,2,ph2);     /// pat[0 to 2]
  58.         if(x==y)
  59.         {
  60.             cout << "Found " << pat << " at i=" << i << endl;
  61.         }
  62.     }
  63.     //for(int i=0;i<n;i++) cout << ph[i] << endl;
  64.     //cout << calcHash(2,4,ph);
  65.  
  66.     return 0;
  67. }
  68.  
  69. /**
  70. 12112121
  71. **/
  72.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found 121 at i=3
Found 121 at i=5
https://ideone.com/K5A1WQ
language:
C++ (gcc 8.3)
created:
15 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!