package algs53; // section 5.3
import stdlib.*;
/* *************************************************************
 *
 *  Compilation:  javac Brtue.java
 *  Execution:    java Brute pattern text
 *
 *  Reads in two strings, the pattern and the input text, and
 *  searches for the pattern in the input text using brute force.
 *
 *  % java Brute abracadabra abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:               abracadabra
 *
 *  % java Brute rab abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:         rab
 *
 *  % java Brute rabrabracad abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:                        rabrabracad

 *
 *  % java Brute bcara abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:                                   bcara
 *
 *  % java Brute abacad abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern: abacad
 *
 ***************************************************************/

public class XBrute {

  /* *************************************************************************
   *  String versions
   ***************************************************************************/

  // return offset of first match or N if no match
  public static int search1(String pat, String txt) {
    int M = pat.length();
    int N = txt.length();

    for (int i = 0; i <= N - M; i++) {
      int j;
      for (j = 0; j < M; j++) {
        if (txt.charAt(i+j) != pat.charAt(j))
          break;
      }
      if (j == M) return i;            // found at offset i
    }
    return N;                            // not found
  }

  // return offset of first match or N if no match
  public static int search2(String pat, String txt) {
    int M = pat.length();
    int N = txt.length();
    int i, j;
    for (i = 0, j = 0; i < N && j < M; i++) {
      if (txt.charAt(i) == pat.charAt(j)) j++;
      else { i -= j; j = 0;  }
    }
    if (j == M) return i - M;    // found
    else        return N;        // not found
  }


  /* *************************************************************************
   *  char[] array versions
   ***************************************************************************/

  // return offset of first match or N if no match
  public static int search1(char[] pattern, char[] text) {
    int M = pattern.length;
    int N = text.length;

    for (int i = 0; i <= N - M; i++) {
      int j;
      for (j = 0; j < M; j++) {
        if (text[i+j] != pattern[j])
          break;
      }
      if (j == M) return i;            // found at offset i
    }
    return N;                            // not found
  }

  // return offset of first match or N if no match
  public static int search2(char[] pattern, char[] text) {
    int M = pattern.length;
    int N = text.length;
    int i, j;
    for (i = 0, j = 0; i < N && j < M; i++) {
      if (text[i] == pattern[j]) j++;
      else { i -= j; j = 0;  }
    }
    if (j == M) return i - M;    // found
    else        return N;        // not found
  }


  // test client
  public static void main(String[] args) {
    //args = new String[] { "abracadabra", "abacadabrabracabracadabrabrabracad" };
    //args = new String[] { "rab",         "abacadabrabracabracadabrabrabracad" };
    //args = new String[] { "bcara",       "abacadabrabracabracadabrabrabracad" };
    //args = new String[] { "rabrabracad", "abacadabrabracabracadabrabrabracad" };
    args = new String[] { "abacad",      "abacadabrabracabracadabrabrabracad" };
    String pat1 = args[0];
    String txt1 = args[1];
    char[] pat2 = pat1.toCharArray();
    char[] txt2 = txt1.toCharArray();

    int offset1a = search1(pat1, txt1);
    int offset2a = search2(pat1, txt1);
    int offset1b = search1(pat2, txt2);
    int offset2b = search2(pat2, txt2);

    // print results
    StdOut.println("text:    " + txt1);

    // from brute force search method 1a
    StdOut.print("pattern: ");
    for (int i = 0; i < offset1a; i++)
      StdOut.print(" ");
    StdOut.println(pat1);

    // from brute force search method 2a
    StdOut.print("pattern: ");
    for (int i = 0; i < offset2a; i++)
      StdOut.print(" ");
    StdOut.println(pat2);

    // from brute force search method 1b
    StdOut.print("pattern: ");
    for (int i = 0; i < offset1b; i++)
      StdOut.print(" ");
    StdOut.println(pat1);

    // from brute force search method 2b
    StdOut.print("pattern: ");
    for (int i = 0; i < offset2b; i++)
      StdOut.print(" ");
    StdOut.println(pat2);
  }
}