HashRK, C++ (gcc) - rextester

HashRK

//g++  7.4.0

//////////////////////////////////////////////////////////////////////////////
//HashRK:Understanding Rabin Karp algorithm for pattern searching
//search() code credit goes to //rathbhupendra,www.geeksforgeeks.com. For more 
//see at https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/
//Class conversion and main driver code are created by Rezaul Hoque on September 06,2022;
//contact:jewelmrh@yahoo.com;Dhaka,Bangladesh;https://rezaulhoque.wordpress.com,https://hoquestake.blogspot.com
//note: codes shared by Rezaul Hoque on rextester are not for sale; they are created and shared to facilitate the algorithm learning process; many like Hoque use this platform to practice programming ;Rezaul hopes his contribution helps others to fine tune their learning;
///////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <cstring>

class RK{
public:
int d=256;
char* c;
char* s;
int q=101;
int M,N;

RK(char* t,char* a){s=t;c=a;
}
void search(){
int M=strlen(c);
int N=strlen(s);
int i,j;
int p=0;//hash value for pattern
int k=0;//hash value for text
int h=1;

for( i=0;i<M-1;i++)
h=(h*d)%q;
for(i=0;i<M;i++)
{
         p = (d*p + c[i])%q;
        k= (d*k + s[i])%q;
    }
//slide pattern over text
for(i=0; i <= N - M; i++)
    {
  
      
        //If the hash values of current substring of text and pattern match then only check for characters one by one 
        if ( p == k)
        {
            //checking characters one by one
            for (j = 0; j < M; j++)
            {
                if (s[i+j] != c[j])
                    break;
            }
  
            
            if (j == M)
                std::cout<<"Pattern found at index "<<i<<" \n";
        }
  if( i < N-M )
        {
            k= (d*(k - s[i]*h) + s[i+M])%q;
  
            
            if (k < 0)
            k= (k+ q);
        }
    }
 }
};

int main()
{
char txt[ ]="Abra Ka Debra,Hokas,Pokus,Gili,Gili";
char a[]="Gili";
RK r(txt,a);
r.search();
return 0;
    
}


run \| edit \| history \| help	0