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