sclass BoyerMoore_chars {
  final static int R = 256;     // the radix
  final int[] right;     // the bad-character skip array
  final char[] pat;      // pattern

  *(S pat) { this(toCharArray(pat)); }
  
  *(char[] *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(char[] 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[i+j]) {
                skip = Math.max(1, j - (right[txt[i+j] & (R-1)]-1));
                break;
            }
        }
        if (skip == 0) ret i;
    }
    ret -1;
  }
}