!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

  }

}