Boyer Moore Algorithm | Good Suffix heuristic | preprocessing for strong good suffix rule ; m is the length of pattern ; if character at position i - 1 is not equivalent to character at j - 1 , then continue searching to right of the pattern for border ; the character preceding the occurrence of t in pattern P is different than the mismatching character in P , we stop skipping the occurrences and shift the pattern from i to j ; Update the position of next border ; p [ i - 1 ] matched with p [ j - 1 ] , border is found . store the beginning position of border ; Preprocessing for case 2 ; set the border position of the first character of the pattern to all indices in array shift having shift [ i ] = 0 ; suffix becomes shorter than bpos [ 0 ] , use the position of next widest border as value of j ; Search for a pattern in given text using Boyer Moore algorithm with Good suffix rule ; s is shift of the pattern with respect to text ; initialize all occurrence of shift to 0 ; do preprocessing ; Keep reducing index j of pattern while characters of pattern and text are matching at this shift s ; If the pattern is present at the current shift , then index j will become - 1 after the above loop ; pat [ i ] != pat [ s + j ] so shift the pattern shift [ j + 1 ] times ; Driver Code
def preprocess_strong_suffix ( shift , bpos , pat , m ) : NEW_LINE INDENT i = m NEW_LINE j = m + 1 NEW_LINE bpos [ i ] = j NEW_LINE while i > 0 : NEW_LINE INDENT while j <= m and pat [ i - 1 ] != pat [ j - 1 ] : NEW_LINE INDENT if shift [ j ] == 0 : NEW_LINE INDENT shift [ j ] = j - i NEW_LINE DEDENT j = bpos [ j ] NEW_LINE DEDENT i -= 1 NEW_LINE j -= 1 NEW_LINE bpos [ i ] = j NEW_LINE DEDENT DEDENT def preprocess_case2 ( shift , bpos , pat , m ) : NEW_LINE INDENT j = bpos [ 0 ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT if shift [ i ] == 0 : NEW_LINE INDENT shift [ i ] = j NEW_LINE DEDENT if i == j : NEW_LINE INDENT j = bpos [ j ] NEW_LINE DEDENT DEDENT DEDENT def search ( text , pat ) : NEW_LINE INDENT s = 0 NEW_LINE m = len ( pat ) NEW_LINE n = len ( text ) NEW_LINE bpos = [ 0 ] * ( m + 1 ) NEW_LINE shift = [ 0 ] * ( m + 1 ) NEW_LINE preprocess_strong_suffix ( shift , bpos , pat , m ) NEW_LINE preprocess_case2 ( shift , bpos , pat , m ) NEW_LINE while s <= n - m : NEW_LINE INDENT j = m - 1 NEW_LINE while j >= 0 and pat [ j ] == text [ s + j ] : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT if j < 0 : NEW_LINE INDENT print ( " pattern ▁ occurs ▁ at ▁ shift ▁ = ▁ % d " % s ) NEW_LINE s += shift [ 0 ] NEW_LINE DEDENT else : NEW_LINE INDENT s += shift [ j + 1 ] NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT text = " ABAAAABAACD " NEW_LINE pat = " ABA " NEW_LINE search ( text , pat ) NEW_LINE DEDENT