/** Simplified version of the Boyer-Moore (BM) algorithm, which uses
    * only the looking-glass and character-jump heuristics.
    * @return Index of the beginning of the leftmost substring of the text
    * matching the pattern, or -1 if there is no match.  */
  public static int BMmatch (String text, String pattern) {
    int[] last = buildLastFunction(pattern);
    int n = text.length();
    int m = pattern.length();
    int i = m -1;
    if (i > n - 1)
      return -1; // no match if pattern is longer than text
    int j = m - 1;
    do {
      if (pattern.charAt(j) == text.charAt(i))
	if (j == 0)
	  return i; // match
	else { // looking-glass heuristic: proceed right-to-left
	  i--;
	  j--;
	}
      else { // character jump heuristic
	i = i + m - Math.min(j, 1 + last[text.charAt(i)]);
	j = m - 1;
      }
    } while (i <= n - 1);
    return -1; // no match
  }
  /** Computation of the auxiliary function used in the BM algorithm.
    * @return Array of size 128 storing the index of the last
    * occurrence of each ASCII character in the pattern.  */
  public static int[] buildLastFunction (String pattern) {
    int[] last = new int[128]; // assume ASCII character set
    for (int i = 0; i < 128; i++) {
      last[i] = -1; // initialize array
    }
    for (int i = 0; i < pattern.length(); i++) {
      last[pattern.charAt(i)] = i; // implicit cast to integer ASCII code
    }
    return last;
  }