text: Boyer Moore Algorithm for Pattern Searching | C Program for Bad Character Heuristic of Boyer Moore String Matching Algorithm ; A utility function to get maximum of two integers ; The preprocessing function for Boyer Moore 's bad character heuristic ; Initialize all occurrences as - 1 ; Fill the actual value of last occurrence of a character ; A pattern searching function that uses Bad Character Heuristic of Boyer Moore Algorithm ; Fill the bad character array by calling the preprocessing function badCharHeuristic ( ) for given pattern ; s is shift of the pattern with respect to text ; there are n - m + 1 potential allignments ; Keep reducing index j of pattern while characters of pattern and text are matching at this shift s ; If the pattern is present at current shift , then index j will become - 1 after the above loop ; Shift the pattern so that the next character in text aligns with the last occurrence of it in pattern . The condition s + m < n is necessary for the case when pattern occurs at the end of text ; Shift the pattern so that the bad character in text aligns with the last occurrence of it in pattern . The max function is used to make sure that we get a positive shift . We may get a negative shift if the last occurrence of bad character in pattern is on the right side of the current character . ; Driver program to test above function
code: # include <limits.h> NEW_LINE # include <string.h> NEW_LINE # include <stdio.h> NEW_LINE # define NO_OF_CHARS  256 NEW_LINE int max ( int a , int b ) { return ( a > b ) ? a : b ; } void badCharHeuristic ( char * str , int size , int badchar [ NO_OF_CHARS ] ) { int i ; for ( i = 0 ; i < NO_OF_CHARS ; i ++ ) badchar [ i ] = -1 ; for ( i = 0 ; i < size ; i ++ ) badchar [ ( int ) str [ i ] ] = i ; } void search ( char * txt , char * pat ) { int m = strlen ( pat ) ; int n = strlen ( txt ) ; int badchar [ NO_OF_CHARS ] ; badCharHeuristic ( pat , m , badchar ) ; int s = 0 ; while ( s <= ( n - m ) ) { int j = m - 1 ; while ( j >= 0 && pat [ j ] == txt [ s + j ] ) j -- ; if ( j < 0 ) { printf ( " pattern occurs at shift = % d " , s ) ; s += ( s + m < n ) ? m - badchar [ txt [ s + m ] ] : 1 ; } else s += max ( 1 , j - badchar [ txt [ s + j ] ] ) ; } } int main ( ) { char txt [ ] = " ABAAABCD " ; char pat [ ] = " ABC " ; search ( txt , pat ) ; return 0 ; }