content: /***************************************************************
   *  Compilation:  javac BoyerMoore.java
   *  Execution:    java BoyerMoore pattern text
   *
   *  Reads in two strings, the pattern and the input text, and
   *  searches for the pattern in the input text using the
   *  bad-character rule part of the Boyer-Moore algorithm.
   *  (does not implement the strong good suffix rule)
   *
   *  % java BoyerMoore abracadabra abacadabrabracabracadabrabrabracad
   *  text:    abacadabrabracabracadabrabrabracad 
   *  pattern:               abracadabra
   *
   *  % java BoyerMoore rab abacadabrabracabracadabrabrabracad
   *  text:    abacadabrabracabracadabrabrabracad 
   *  pattern:         rab
   *
   *  % java BoyerMoore bcara abacadabrabracabracadabrabrabracad
   *  text:    abacadabrabracabracadabrabrabracad 
   *  pattern:                                   bcara
   *
   *  % java BoyerMoore rabrabracad abacadabrabracabracadabrabrabracad
   *  text:    abacadabrabracabracadabrabrabracad
   *  pattern:                        rabrabracad
   *
   *  % java BoyerMoore abacad abacadabrabracabracadabrabrabracad
   *  text:    abacadabrabracabracadabrabrabracad
   *  pattern: abacad
   *
   ***************************************************************/
  
  public class BoyerMoore {
      private final int R;     // the radix
      private int[] right;     // the bad-character skip array
  
      private char[] pattern;  // store the pattern as a character array
      private String pat;      // or as a string
  
      // pattern provided as a string
      public BoyerMoore(String pat) {
          this.R = 256;
          this.pat = pat;
  
          // position of rightmost occurrence of c in the pattern
          right = new int[R];
          for (int c = 0; c < R; c++)
              right[c] = -1;
          for (int j = 0; j < pat.length(); j++)
              right[pat.charAt(j)] = j;
      }
  
      // pattern provided as a character array
      public BoyerMoore(char[] pattern, int R) {
          this.R = R;
          this.pattern = new char[pattern.length];
          for (int j = 0; j < pattern.length; j++)
              this.pattern[j] = pattern[j];
  
          // position of rightmost occurrence of c in the pattern
          right = new int[R];
          for (int c = 0; c < R; c++)
              right[c] = -1;
          for (int j = 0; j < pattern.length; j++)
              right[pattern[j]] = j;
      }
  
      // return offset of first match; N if no match
      public int search(String txt) {
          int M = pat.length();
          int N = txt.length();
          int skip;
          for (int i = 0; i <= N - M; i += skip) {
              skip = 0;
              for (int j = M-1; j >= 0; j--) {
                  if (pat.charAt(j) != txt.charAt(i+j)) {
                      skip = Math.max(1, j - right[txt.charAt(i+j)]);
                      break;
                  }
              }
              if (skip == 0) return i;    // found
          }
          return N;                       // not found
      }
  
  
      // return offset of first match; N if no match
      public int search(char[] text) {
          int M = pattern.length;
          int N = text.length;
          int skip;
          for (int i = 0; i <= N - M; i += skip) {
              skip = 0;
              for (int j = M-1; j >= 0; j--) {
                  if (pattern[j] != text[i+j]) {
                      skip = Math.max(1, j - right[text[i+j]]);
                      break;
                  }
              }
              if (skip == 0) return i;    // found
          }
          return N;                       // not found
      }
  
  
  
      // test client
      public static void main(String[] args) {
          String pat = args[0];
          String txt = args[1];
          char[] pattern = pat.toCharArray();
          char[] text    = txt.toCharArray();
  
          BoyerMoore boyermoore1 = new BoyerMoore(pat);
          BoyerMoore boyermoore2 = new BoyerMoore(pattern, 256);
          int offset1 = boyermoore1.search(txt);
          int offset2 = boyermoore2.search(text);
  
          // print results
          StdOut.println("text:    " + txt);
  
          StdOut.print("pattern: ");
          for (int i = 0; i < offset1; i++)
              StdOut.print(" ");
          StdOut.println(pat);
  
          StdOut.print("pattern: ");
          for (int i = 0; i < offset2; i++)
              StdOut.print(" ");
          StdOut.println(pat);
      }
  }
  