Advertisement
spider68

Search Pattern (Rabin-Karp Algorithm)

Dec 17th, 2021
1,094
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. Solution
  2. {
  3.     int mul=256,mod=107;
  4.     public:
  5.         vector <int> search(string pat, string txt)
  6.         {
  7.             int lenTxt=txt.length(),lenPat=pat.length();
  8.             if(lenTxt<lenPat)return {-1};
  9.             vector<int>pos;
  10.            
  11.             int patHash=0,txtHash=0,hash=1;
  12.            
  13.             for(int i=1;i<=lenPat-1;i++){
  14.                 hash=(hash*mul)%mod;
  15.             }
  16.            
  17.             for(int i=0;i<lenPat;i++){
  18.                 patHash=(patHash*mul + pat[i])%mod;
  19.                 txtHash=(txtHash*mul + txt[i])%mod;
  20.             }
  21.            
  22.             for(int i=0;i<=lenTxt-lenPat;i++){
  23.                
  24.                 if(patHash==txtHash){
  25.                     int present=true;
  26.                     for(int j=0;j<lenPat;j++){
  27.                         if(txt[i+j] != pat[j]){
  28.                             present=false;
  29.                             break;
  30.                         }    
  31.                     }
  32.                     if(present==true)pos.push_back(i+1);
  33.                 }
  34.                
  35.                 if(i<lenTxt-lenPat){
  36.                     txtHash=((txtHash- (txt[i]*hash)%mod )*mul + txt[i+lenPat])%mod;
  37.                     if(txtHash<0)txtHash+=mod;
  38.                 }
  39.             }
  40.             if(pos.size()==0)return {-1};
  41.             return pos;
  42.         }
  43.      
  44. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement