Boyer Moore Algorithm for Pattern Searching | Python3 Program for Bad Character Heuristic of Boyer Moore String Matching Algorithm ; The preprocessing function for Boyer Moore 's bad character heuristic   ; Initialize all occurrence as - 1 ; Fill the actual value of last occurrence ; A pattern searching function that uses Bad Character Heuristic of Boyer Moore Algorithm ; create the bad character list 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
NO_OF_CHARS = 256 NEW_LINE def badCharHeuristic ( string , size ) : NEW_LINE INDENT badChar = [ - 1 ] * NO_OF_CHARS NEW_LINE for i in range ( size ) : NEW_LINE INDENT badChar [ ord ( string [ i ] ) ] = i ; NEW_LINE DEDENT return badChar NEW_LINE DEDENT def search ( txt , pat ) : NEW_LINE INDENT m = len ( pat ) NEW_LINE n = len ( txt ) NEW_LINE badChar = badCharHeuristic ( pat , m ) NEW_LINE s = 0 NEW_LINE while ( s <= n - m ) : NEW_LINE INDENT j = m - 1 NEW_LINE while j >= 0 and pat [ j ] == txt [ s + j ] : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT if j < 0 : NEW_LINE INDENT print ( " Pattern ▁ occur ▁ at ▁ shift ▁ = ▁ { } " . format ( s ) ) NEW_LINE s += ( m - badChar [ ord ( txt [ s + m ] ) ] if s + m < n else 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT s += max ( 1 , j - badChar [ ord ( txt [ s + j ] ) ] ) NEW_LINE DEDENT DEDENT DEDENT def main ( ) : NEW_LINE INDENT txt = " ABAAABCD " NEW_LINE pat = " ABC " NEW_LINE search ( txt , pat ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT main ( ) NEW_LINE DEDENT