Friday 11 April 2014

Program In C++ TO Implement Rabin karp String Matching Algorithm

#include<iostream.h>
#include<conio.h>
#include<math.h>
void main()
{ int T[30],P[10],i,n,m,p,to,s,flag=0,j,d=10,q=11,h;
clrscr();
cout<<"Enter The Length Of Text: ";
cin>>n;
cout<<"\nEnter Text: ";
for(i=1;i<=n;i++)
cin>>T[i];
cout<<"\nEnter The Length Of Pattern: ";
cin>>m;
cout<<"\nEnter Pattern: ";
for(i=1;i<=m;i++)
cin>>P[i];
h=pow(d,m-1);
h=h%q;
p=to=0;
for(i=1;i<=m;i++)
{ p=((d*p)+P[i])%q;
to=((d*to)+T[i])%q;
for(s=0;s<=n-m;s++)
if(p==to)
{
for(i=s+1;i<=s+m;i++)
{
 for(j=1;j<=m;j++)
 {
  if(T[s+j]==P[j])
   {
    flag=1;
    continue ;
   }
  else
  {
   flag=0;
   break;
  }
 }
}
if(flag==1)
 {
  cout<<"\nPattern Occurs With Shift: "<<s<<"\n";
 }
}
if(s<n-m)
{ to=(d*(to-(T[s+1]*h)))+(T[s+m+1]%q);}
}
getch();
}