/**
 *  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
  final int[] right;     // the bad-character skip array
  final char[] pat;      // pattern

  *(S pat) {
    this.pat = toCharArray(pat);

    // position of rightmost occurrence of c in the pattern
    right = new int[R];
    for (int j = 0; j < pat.length; j++)
        right[pat[j] & (R-1)] = j+1;
  }

  /**
   * 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) {
    if (txt == null) ret -1;
    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[j] != txt.charAt(i+j)) {
          skip = Math.max(1, j - (right[txt.charAt(i+j) & (R-1)]-1));
          break;
        }
      }
      if (skip == 0) ret i;
    }
    ret -1;
  }
}