/**
 *  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="https://algs4.cs.princeton.edu/53substring">Section 5.3</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *  Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne. 
 *  Last updated: Fri Oct 20 12:50:46 EDT 2017.
 */
sclass BoyerMooreStringSearch {
  final static int R = 256;     // the radix
  int[] right;     // the bad-character skip array
  S pat;      // pattern

  *(S 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) & (R-1)] = 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; -1 if no such match
   */
  int search(S 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) & (R-1)]);
                  break;
              }
          }
          if (skip == 0) ret i;
      }
      ret -1;
  }
}