Implementation of Rabin-Karp String Matching Algorithm in C

#include<stdio.h>
#include<string.h>
#include<math.h>
char text[100],pattern[100];
void rabinKarpMatcher(int d,int q)
{
 int m,n,i,s,h,p,t;
 n=strlen(text);
 m=strlen(pattern);
 h=pow(d,m-1);
 h=h % q;
 p=0;
 t=0;
 printf("m=%d\tn=%d\th=%d\tq=%d\n",m,n,h,q);
 for(i=0;i<m;i++)           //Preprocessing
 {
  p=(d*p+pattern[i])%q;
  t=(d*t+text[i])%q;
  printf("i=%d\tp=%d\tt=%d\n",i,p,t);
 }
 for(s=0;s<=(n-m);s++)   //Matching..
 {
  printf("s=%d\t",s);
  if(p==t)     //Possibility of match found
  {
   for (i = 0; i < m; i++)
   {
    if (text[i+s] != pattern[i])
     break;
   }
   if (i==m)

    printf("Pattern occours with shift %d\n",s);
  }

  if(s<(n-m))
  {
   t=(d*(t-text[s]*h)+text[s+m]);     //Updating the value of t for the next pass
   t=t % q;
   if (t < 0)   //to avoid negative values
   t = (t + q);
  }
  printf("t=%d\n",t);


 }
}
void main()
{
 int x;
 printf("Enter the text ");
 scanf("%s",text);
 printf("Enter the Pattern ");
 scanf("%s",pattern);
 rabinKarpMatcher(10,3);
}



Test 1:
Enter the text aabcaaabcbacb
Enter the Pattern abc
m=3   n=13    h=1     q=3
i=0     p=1     t=1
i=1     p=0     t=2
i=2     p=0     t=1
s=0     t=0
s=1     Pattern occours with shift 1  t=0
s=2     t=2
s=3     t=0
s=4     t=1
s=5     t=0
s=6     Pattern occours with shift 6  t=1
s=7     t=0
s=8     t=0
s=9     t=0
s=10    t=0


Test 2:
Enter the text 314265
Enter the Pattern 42
m=2   n=6     h=1     q=3
i=0     p=1     t=0
i=1     p=0     t=1
s=0     t=2
s=1     t=0
s=2     Pattern occours with shift 2  t=2
s=3     t=2
s=4     t=2

Comments

Popular posts from this blog

Hack WhatsApp Accounts Easy – Whatsapp Hack Online 2017

How to hack a kik account

Real way to earn money online