/** Knuth-Morris-Pratt algorithm from Introduction to Algorithms by 
Cormen, Leiserson, Rivest
*/

import java.util.*;

public class KMP
{
    private static char[] c; // The pattern we are looking for
    private static int[] z;  // The prefix distance for the pattern

    /** Compute the array z of length p.length() such that
	z[0] is 0, and for 0<j<p.length, z[j] is largest k
	such that p[0,k] is a suffix of p[0,j]
    */
    public static void computePrefixFunction(String p) {
	int m = p.length();
	c = p.toCharArray();
	z = new int[m];
	z[0] = 0;
	int k = 0;
	for (int q = 1; q < m; q++) {
	    while (k > 0 && c[k] != c[q])
		k = z[k]-1;
	    if (c[k] == c[q])
		k++;
	    z[q] = k;
	}
    }

    public static void KMPMatcher(String text) {
	int n = text.length();
	int m = c.length;
	int q = 0;
	for (int i = 0; i < n; i++) {
	    while (q > 0 && c[q] != text.charAt(i))
		q = z[q-1];
	    if (c[q] == text.charAt(i))
		q++;
	    if (q == m) {
		System.out.println("Match with shift " + (i-m+1));
		q = z[q-1];
	    }
	}
    }

    public static void main(String[] args) {
	if (args.length != 1) {
	    System.out.println("usage: java KMP pattern");
	    return;
	}
	computePrefixFunction(args[0]);
	System.out.println(" k  \t z[k]");
	for (int k = 0; k < z.length; k++)
	    System.out.printf("%3d \t %3d\n", k, z[k]); 
	Scanner sc = new Scanner(System.in);
	while (true) {
	    System.out.print("Enter text to be matched: ");
	    String aLine = sc.nextLine();
	    if (aLine.length() == 0) break;
	    KMPMatcher(aLine);
	}
    }
}