#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
