KMP算法
KMP原理
KMPnext
public static void main(String[] args) { String a="VERDI"; char[] pattern=a.toCharArray(); int[] prefix=next(pattern); String b="AXIVVERDIYERDIAN"; char[] original=b.toCharArray(); System.out.println(SearchPattern(original, pattern)); } public static int SearchPattern(char[] original,char[] pattern){ int[] next=next(pattern); int j = 0; for (int i = 0; i < original.length; i++) { while (j > 0 && original[i]!= pattern[j]) j = next[j-1]; if (original[i] == pattern[j]) j++; if (j == pattern.length) { //System.out.println("find at position " + (i - j)); //System.out.println(original.subSequence(i-j+ 1, i + 1)); //j = next[j]; return i-j+1; } } return 0; } public static int[] next(char[] pattern){ int length=pattern.length; int[] prefix=new int[length]; prefix[0]=0; for(int i=1; i<length; i++) { int k=prefix[i-1]; //不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推 while( pattern[i] != pattern[k] && k!=0 ) k=prefix[k-1]; //继续递归 if( pattern[i] == pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++ prefix[i]=k+1; else prefix[i]=0; //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0 } return prefix; } }