/**
 *  Finds the first occurrence of a pattern string
 *  in a text string. Converts all to uppercase.
 *  <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_upper {
  final static int R = 256;     // the radix
  final int[] right;     // the bad-character skip array
  final char[] pat;      // pattern

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

    // position of rightmost occurrence of c in the pattern
    right = new int[R];
    for (int j = 0; j < this.pat.length; j++)
        right[this.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 diff = txt.length()-m;
    int skip;
    for (int i = 0; i <= diff; i += skip) {
      skip = 0;
      for (int j = m-1; j >= 0; j--) {
        int c = upper(txt.charAt(i+j));
        if (pat[j] != c) {
          skip = Math.max(1, j - (right[c & (R-1)]-1));
          break;
        }
      }
      if (skip == 0) ret i;
    }
    ret -1;
  }
  
  bool containedIn(S txt) {
    ret search(txt) >= 0;
  }
}