C++ program to perform robin karp string matching

admin May 25, 2013 0 Comments

       WRITE A PROGRAM TO PERFORM ROBIN KARP STRING MATCHING

#include<iostream.h>
#include<conio.h>
#include<math.h>
void main()
{int str[7],mods[7],i,j,len=0,temp[7],substrmod,substrdiv[7],k=0,flag=0;
longint substr1,substr;
clrscr();
for(i=0;i<7;i++)
{temp[i]=0;
mods[i]=-1;
substrdiv[i]=0;
}
cout<<"Enter the sequence<7 character long and use space between 2 characters>:\n";
for(i=0;i<7;i++)
cin>>str[i];
cout<<"\nEnter the substring you want to search in the string:\n";
cin>>substr;
substr1=substr;
while(substr1!=0)
{substr1=substr1/10;
len++;
}
substrmod=substr%13;
i=1;
substr1=substr;
while(i<=len)
{substrdiv[len-i]=substr1%10;
substr1=substr1/10;
i++;
}
for(i=0;i<=(7-len);i++)
{temp[19]=0;
for(j=0;j<len;j++)
{temp[j]=str[i+j];
}
for(j=0;j<len;j++)
{temp[j]=temp[j]*pow(10,(len-(j+1)));
}
for(j=0;j<len;j++)
{temp[19]=temp[19]+temp[j];
}
mods[i]=temp[19]%13;
}
i=0;
while(mods[i]!=-1 && i<7)
{k=0;
if(mods[i]==substrmod)
{for(j=0;j<len;j++)
{if(str[i+j]==substrdiv[j])
k++;
}
if(k==len)
{cout<<"\nString found at position "<<i+1;
flag=1; } }
i++; }
if(flag==0)
cout<<"\nString not found";
getch(); }

OUTPUT :

output for robin carp string matching

Leave a Reply