import java.util.Arrays;

public class KMP {
	public static void getNext(char[] str,int[] next) {
		next[0]=-1;
		int i=0,j=-1;
		while(i<str.length) {
			if(j==-1) {
				i++;
				j++;
			}else if(str[i]==str[j]) {
				i++;
				j++;
				next[i]=j;
			}else {
				j=next[j];
			}
		}
	}
	public static int search(char[] str1,char[] str2,int[] next) {
		int i=0,j=0;
		while(i<str1.length && j<str2.length) {
			if(j==-1 || str1[i]==str2[j]) {
				i++;
				j++;
			}else {
				j=next[j];
			}
		}
		if(j==str2.length) {
			return i-j;
		}else {
			return -1;
		}
	}
	
	
	public static void main(String[] args) {
		String str1="ABCABCAABCABCD";
		String strPattern="ABCABCD";
		int[] next=new int[strPattern.length()];
		getNext(strPattern.toCharArray(),next);
		int i=search(str1.toCharArray(),strPattern.toCharArray(),next);
		System.out.println(Arrays.toString(next));
		System.out.println(i);
	}
}