!7

/**
 * Takes a pattern string and an input string as command-line arguments;
 * searches for the pattern string in the text string; and prints
 * the first occurrence of the pattern string in the text string.
 *
 * @param args the command-line arguments
 */
public static void main(S[] args) {
  tt();
  
  if (empty(args)) args = new S[] {"abc", "bcabc"};
  String pat = args[0];
  String txt = args[1];
  char[] pattern = pat.toCharArray();
  char[] text    = txt.toCharArray();

  BoyerMoore boyermoore1 = new BoyerMoore(pat);
  BoyerMoore boyermoore2 = new BoyerMoore(pattern, 256);
  int offset1 = boyermoore1.search(txt);
  int offset2 = boyermoore2.search(text);

  // print results
  println("text:    " + txt);

  printNoNewLine("pattern: ");
  for (int i = 0; i < offset1; i++)
      printNoNewLine(" ");
  println(pat);

  printNoNewLine("pattern: ");
  for (int i = 0; i < offset2; i++)
      printNoNewLine(" ");
  println(pat);
}


/**
 *  The {@code BoyerMoore} class 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 BoyerMoore {
  final int R;     // the radix
  int[] right;     // the bad-character skip array

  char[] pattern;  // store the pattern as a character array
  S pat;      // or as a string

  *(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)] = j;
  }

  /**
   * Preprocesses the pattern string.
   *
   * @param pattern the pattern string
   * @param R the alphabet size
   */
  public BoyerMoore(char[] pattern, int R) {
      this.R = R;
      this.pattern = new char[pattern.length];
      for (int j = 0; j < pattern.length; j++)
          this.pattern[j] = pattern[j];

      // 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 < pattern.length; j++)
          right[pattern[j]] = 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; n if no such match
   */
  public int search(String 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)]);
                  break;
              }
          }
          if (skip == 0) return i;    // found
      }
      return n;                       // not found
  }


  /**
   * Returns the index of the first occurrrence of the pattern string
   * in the text string.
   *
   * @param  text the text string
   * @return the index of the first occurrence of the pattern string
   *         in the text string; n if no such match
   */
  public int search(char[] text) {
      int m = pattern.length;
      int n = text.length;
      int skip;
      for (int i = 0; i <= n - m; i += skip) {
          skip = 0;
          for (int j = m-1; j >= 0; j--) {
              if (pattern[j] != text[i+j]) {
                  skip = Math.max(1, j - right[text[i+j]]);
                  break;
              }
          }
          if (skip == 0) return i;    // found
      }
      return n;                       // not found
  }
}