java|KMP算法实现（java日记） java|算法

一个冷知识：
kmp的next数组有两种写法，一种是教科书上常用的以-1，0为开头的，一种是竞赛中常用的以0为开头的，两种所求next数组不同，后续使用方式也不同，代码自然也不尽相同，但是思路一致，找出一种适合自己的写法理解记忆就好，不用过于纠结。
代码如下：

public class KMP算法 { public static void main(String[] args) { String s1="ABCDABEEEEABCDABCD"; String s2="ABCDABCD"; int index=KMP(s1,s2); System.out.println(index); System.out.println(s1.charAt(index)); } public static int KMP(String s1,String s2){ char[] c1=s1.toCharArray(); char[] c2=s2.toCharArray(); int[] next=getNext(c2); int i=0; int j=0; while (i0){ j=next[j]; } else { i++; } } return j==c2.length?i-j:-1; } public static int[] getNext(char[] c){ int len=c.length; if(len==1){ return new int[]{-1}; } int[] next=new int[len]; next[0]=-1; next[1]=0; int i=2; //判断的是i前面字符串的前缀和后缀 int cn=0; //cn代表前一个位置的最大长度，同样也是在c中的下标 while (i0){ cn=next[cn]; } else { next[i++]=0; }} return next; }}

【java|KMP算法实现（java日记）】