精华之处：求next数组（自动机）
KMP与getNext方法相同，只有 next[suffix] = prefix; //1不同
next数组求解方法：
1.覆盖表：求前缀、后缀公共部分最大长度
2.next数组为覆盖表右移一位。
public class KMP {
public static int KMP(String s, String t) {
int i = 0;
int j = 0;
//得到next数组
int[] next = getNext(t);
while (i < s.length() && j < t.length()) {
if (j == -1 || s.charAt(i) == t.charAt(j)) {
i++;
j++;
}else {
//根据next数组的指示j进行回溯，而i永远不会回溯
j = next[j];
}
}
if (j == t.length()) {
return i - j;
}else {
return -1;
}
}
/**
* next指的是KMP主算法中的j该回溯到哪个位置
*其值就是当前位置之前的可覆盖子串最大长度；
*
*所以代码就是找可覆盖子串的最大长度，
*其实就是：模式串自己对自己的匹配
*用prefix所指的串去匹配suffix所指的串
*所以代码和kmp的主算法是类似的
* @param t
* @return
*/
public static int[] getNext(String t) {
int[] next = new int[t.length()];
next[0] = -1;
int suffix = 0; // 后缀
int prefix = -1; // 前缀
while (suffix < t.length() - 1) {
//若前缀索引为-1或相等，则前缀后缀索引均+1
if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
++prefix;
++suffix;
next[suffix] = prefix; //1
}else {
prefix = next[prefix]; //2
}
}
return next;
}
/**
*改进的就是可覆盖子串的后一项，可能和当前项一样
*如ABCDABD,第二个AB不该是0，1，而是-1，0
* @param t
* @return
*/
public static int[] getNext2(String t) {
int[] next = new int[t.length()];
next[0] = -1;
int suffix = 0; // 后缀
int prefix = -1; // 前缀
while (suffix < t.length() - 1) {
//若相等或前缀索引为-1，则前缀后缀索引均+1
if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
++prefix;
++suffix;
//改进的地方
if (t.charAt(prefix) == t.charAt(suffix)) {
next[suffix] = next[prefix];
}else {
next[suffix] = prefix;
}
}else {
prefix = next[prefix];
}
}
return next;
}
}
网友评论