code: package edu.berkeley.cs.jqf.examples.algs4;
  
  /**
   *  The {@code BoyerMoore} class finds the first occurrence of a pattern string
   *  in a text string.
   *  <p>
   *  This implementation uses the Boyer-Moore algorithm (with the bad-character
   *  rule, but not the strong good suffix rule).
   *  <p>
   *  For additional documentation,
   *  see <a href="http://algs4.cs.princeton.edu/53substring">Section 5.3</a> of
   *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
   *
   *  Source: http://algs4.cs.princeton.edu/53substring/BoyerMoore.java
   */
  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
  
      /**
       * Preprocesses the pattern string.
       *
       * @param pat the pattern 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;
      }
  
      /**
       * Preprocesses the pattern string.
       *
       * @param pattern the pattern string
       * @param R the alphabet size
       */
      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;
      }
  
      /**
       * Returns the index of the first occurrrence of the pattern string
       * in the text string.
       *
       * @param  txt the text string
       * @return the index of the first occurrence of the pattern string
       *         in the text string; n if no such 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
      }
  
  
      /**
       * Returns the index of the first occurrrence of the pattern string
       * in the text string.
       *
       * @param  text the text string
       * @return the index of the first occurrence of the pattern string
       *         in the text string; n if no such 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
      }
  }
  