当前位置 博文首页 > Aaron_Yang：KMP算法之next数组
??????在KMP算法中有个数组，叫做前缀数组，也有的叫next数组，每一个子串有一个固定的next数组，它记录着字符串匹配过程中失配情况下可以向前多跳几个字符，当然它描述的也是子串的对称程度，程度越高，值越大，当然之前可能出现再匹配的机会就更大。
??????这个next数组的求法是KMP算法的关键，能不能掌握它非常的重要。
个人总结：
next【i】是最大相同前后缀的长度，回溯之后i=next【i】, 即新的j指向了前缀 (ab)的后面一个char(c），滑动距离就是i-next【i】，next【i】越小，滑动距离越大，next【i】越大，滑动距离越小。然后就是next【0】设计成-1的精妙之处就是公共部分是i++，j++，如果第一个char就失配，KMP退化成BF，即i=i-j+1，j=0。第一次i++和j++就失配了，失配了去找next【j】嘛，然后j = j-next【0】，next【0】是-1即可。next表的意义就是，j++的时候，如果每次都要向前扫描找是否有相同前后缀并记录长度，这就很难受，因为可以在任意一个时刻失配。
package com.southwind;
public class next_Array {
public static void main(String[] args) {
String str = "abcdabd";
int next[] = new int[8];
getNext(str, next);
for (int a : next)
System.out.print(a + " ");
}
public static void getNext(String s, int next[]) {
int i = -1; //i前缀
int j = 0; //j后缀
next[0] = -1;
char a[] = s.toCharArray();
while (j < a.length) {
if (i == -1 || a[i] == a[j]) {
i++;
j++;
next[j] = i;
} else
i = next[i];
}
}
}
结果：
