C Program to search the perticulur pattern in the string using Horspool method


Levels of difficulty: / perform operation:

C Program to find the substring in a String using the Horspool method. This algorithm uses the Brute-Forse method which searches the text between 0 and n-m, and after each cycle it shifts the pattern by one position to the right.


C Program

#include<stdio.h>
#include<string.h>
#include<conio.h>
#define MAX 500
int t[MAX];
void shifttable(char p[]) {
	int i,j,m;
	m=strlen(p);
	for (i=0;i<MAX;i++)
	  t[i]=m;
	for (j=0;j<m-1;j++)
	  t[p[j]]=m-1-j;
}
int horspool(char src[],char p[]) {
	int i,j,k,m,n;
	n=strlen(src);
	m=strlen(p);
	printf("\nLength of text=%d",n);
	printf("\n Length of pattern=%d",m);
	i=m-1;
	while(i<n) {
		k=0;
		while((k<m)&&(p[m-1-k]==src[i-k]))
		   k++;
		if(k==m)
		   return(i-m+1); else
		   i+=t[src[i]];
	}
	return -1;
}
void main() {
	char src[100],p[100];
	int pos;
	clrscr();
	printf("Enter the text in which pattern is to be searched:\n");
	gets(src);
	printf("Enter the pattern to be searched:\n");
	gets(p);
	shifttable(p);
	pos=horspool(src,p);
	if(pos>=0)
	  printf("\n The desired pattern was found starting from position %d",pos+1); else
	  printf("\n The pattern was not found in the given text\n");
	getch();
}





Quantitative Aptitude
Reasoning
Programming
Interview