package algs53;
import  stdlib.*;

/* *************************************************************
 *
 *  Compilation:  javac KMP.java
 *  Execution:    java KMP pattern text
 *
 *  Reads in two strings, the pattern and the input text, and
 *  searches for the pattern in the input text using the
 *  KMP algorithm.
 *
 *  % java KMP abracadabra abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:               abracadabra
 *
 *  % java KMP rab abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:         rab
 *
 *  % java KMP bcara abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:                                   bcara
 *
 *  % java KMP rabrabracad abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern:                        rabrabracad
 *
 *  % java KMP abacad abacadabrabracabracadabrabrabracad
 *  text:    abacadabrabracabracadabrabrabracad
 *  pattern: abacad
 *
 ***************************************************************/

public class KMP {
	private final int R;       // the radix
	private int[][] dfa;       // the KMP automoton

	private char[] pattern;    // either the character array for the pattern
	private String pat;        // or the pattern string

	// create the DFA from a String
	public KMP(String pat) {
		this.R = 256;
		this.pat = pat;

		// build DFA from pattern
		int M = pat.length();
		dfa = new int[R][M];
		dfa[pat.charAt(0)][0] = 1;
		for (int X = 0, j = 1; j < M; j++) {
			for (int c = 0; c < R; c++)
				dfa[c][j] = dfa[c][X];     // Copy mismatch cases.
			dfa[pat.charAt(j)][j] = j+1;   // Set match case.
			X = dfa[pat.charAt(j)][X];     // Update restart state.
		}
	}

	// create the DFA from a character array over R-character alphabet
	public KMP(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];

		// build DFA from pattern
		int M = pattern.length;
		dfa = new int[R][M];
		dfa[pattern[0]][0] = 1;
		for (int X = 0, j = 1; j < M; j++) {
			for (int c = 0; c < R; c++)
				dfa[c][j] = dfa[c][X];     // Copy mismatch cases.
			dfa[pattern[j]][j] = j+1;      // Set match case.
			X = dfa[pattern[j]][X];        // Update restart state.
		}
	}

	// return offset of first match; N if no match
	public int search(String txt) {

		// simulate operation of DFA on text
		int M = pat.length();
		int N = txt.length();
		int i, j;
		for (i = 0, j = 0; i < N && j < M; i++) {
			j = dfa[txt.charAt(i)][j];
		}
		if (j == M) return i - M;    // found
		return N;                    // not found
	}


	// return offset of first match; N if no match
	public int search(char[] text) {

		// simulate operation of DFA on text
		int M = pattern.length;
		int N = text.length;
		int i, j;
		for (i = 0, j = 0; i < N && j < M; i++) {
			j = dfa[text[i]][j];
		}
		if (j == M) return i - M;    // found
		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();

		KMP kmp1 = new KMP(pat1);
		int offset1 = kmp1.search(txt1);

		KMP kmp2 = new KMP(pat2, 256);
		int offset2 = kmp2.search(txt2);

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

		StdOut.print("pattern: ");
		for (int i = 0; i < offset1; i++)
			StdOut.print(" ");
		StdOut.println(pat1);

		StdOut.print("pattern: ");
		for (int i = 0; i < offset2; i++)
			StdOut.print(" ");
		StdOut.println(pat2);
	}
}