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); } }