Question

How many character comparisons will the BMH algorithm perform to solve the pattern search problem shown below?

text:    my next door neighbor is a witch
pattern: is

explain c language

Answer 1

Boyer Moore Horspool :- Boyer Moore Horspool Algorithm is a pattren searching algorithm, basically BMH is uses two approaches to find substrings in a string.

Do not forget to like my work.

1)Bad Character Heuristic

2)Good Suffix Heuristic

text:    my next door neighbor is a witch
pattern: is

I am going to solve this problem using Bad Character Heuristic.

In simple bad character means current character of pattern is not matched with character of string .

Algorithm:-

on wrong match, we shift the pattern until –
1) The wrong match becomes a match
2) Pattern N move past the wrong matched character.

Program in C:-

#include<stdio.h>
# include <string.h>
# include <limits.h>

# define CHAR 140

int max (int first, int second) {
return (first > second)? first: second;
}

void BMH(char *str, int n,int mismatch[CHAR])
{
   int i;
   for (i = 0; i < CHAR; i++)
mismatch[i] = -1;
   for (i = 0; i < n; i++)
       mismatch[(int) str[i]] = i;
}
void search( char *text, char *pattern)
{
   int c = strlen(pattern);
   int d = strlen(text);
int mismatch[CHAR];
   BMH(pattern, c, mismatch);
   int a = 0;
   while(a <= (d - c))
   {
       int j = c-1;
       while(j >= 0 && pattern[j] == text[a+j])
           j--;
       if (j < 0)
       {
           printf("Character compared:=%d",a);
a += (a+c < d)? c-mismatch[text[a+c]] : 1;

       }
       else
           a += max(1, j - mismatch[text[a+j]]);
   }
}
int main(){
   char text[ ] = "my next door neighbor is a witch";
   char pattern[ ] = "is";
   search(text, pattern);
   return 0;
}

Output:-

Character compared:22

Total 22 characters are compared to match pattern

Please hit that thumbs-up or like button to motivate me.>3

Thank you!!