Boyer Moore Algorithm | Good Suffix heuristic | Java program for Boyer Moore Algorithm with Good Suffix heuristic to find pattern in given text string ; 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
class GFG { static void preprocess_strong_suffix ( int [ ] shift , int [ ] bpos , char [ ] pat , int m ) { int i = m , j = m + 1 ; bpos [ i ] = j ; while ( i > 0 ) { while ( j <= m && pat [ i - 1 ] != pat [ j - 1 ] ) { if ( shift [ j ] == 0 ) shift [ j ] = j - i ; j = bpos [ j ] ; } i -- ; j -- ; bpos [ i ] = j ; } } static void preprocess_case2 ( int [ ] shift , int [ ] bpos , char [ ] pat , int m ) { int i , j ; j = bpos [ 0 ] ; for ( i = 0 ; i <= m ; i ++ ) { if ( shift [ i ] == 0 ) shift [ i ] = j ; if ( i == j ) j = bpos [ j ] ; } } static void search ( char [ ] text , char [ ] pat ) { int s = 0 , j ; int m = pat . length ; int n = text . length ; int [ ] bpos = new int [ m + 1 ] ; int [ ] shift = new int [ m + 1 ] ; for ( int i = 0 ; i < m + 1 ; i ++ ) shift [ i ] = 0 ; preprocess_strong_suffix ( shift , bpos , pat , m ) ; preprocess_case2 ( shift , bpos , pat , m ) ; while ( s <= n - m ) { j = m - 1 ; while ( j >= 0 && pat [ j ] == text [ s + j ] ) j -- ; if ( j < 0 ) { System . out . printf ( "pattern occurs at shift = %dNEW_LINE", s); s += shift [ 0 ] ; } else s += shift [ j + 1 ] ; } } public static void main ( String [ ] args ) { char [ ] text = " ABAAAABAACD " . toCharArray ( ) ; char [ ] pat = " ABA " . toCharArray ( ) ; search ( text , pat ) ; } }