AdSenseHeader


                                         HARSPOOL'S ALGORITHAM      

#include<stdio.h>
#include<conio.h>
#include<string.h>
int t[30];
void shifttable(char[],int);
int matchtable(char[],char[]);
void main()
{
char text[50];
char pat[40];
int m;

int i,l,j,tlen;
clrscr();
printf("enter the pattern....");
gets(pat);
printf("enter the text.......");
gets(text);
l=strlen(pat);
shifttable(pat,l);
m=matchtable(pat,text);
if(m!=-1)
{
printf("\n\n");
printf("\nthe string is found at\t %d",m+1);
}
else
{
 printf("\n");
printf("\nthe string is not found");
}
getch();
}
void shifttable(char pat[30],int l)
{
char c[30];
int i,j;
for(i=65,j=0;i<91;i++,j++)
{
c[j]=i;
t[c[j]]=l;
}
c[j]=' ';
t[c[j]]=l;
for(j=0;j<l-1;j++)
{
t[pat[j]]=(l-1)-j;
}
for(i=0;i<27;i++)
{
printf("%2c",c[i]);
}
printf("\n");
for(i=0;i<27;i++)
{
printf("%2d",t[c[i]]);
}
}
int matchtable(char pat[], char text[])
{
int l,tlen,i;
l=strlen(pat);
tlen=strlen(text);
i=l-1;
while(i<=tlen-1)
{
int k;
k=0;
while((k<=l-1)&&(pat[l-1-k]==text[i-k]))
k++;
if(k==l)
{
return i-l+1;
}
else
i=i+t[text[i]];
}
return -1;
}



0 comments:

Post a Comment

 
Top