当源字符串 src 和 模式串 pat 不匹配的时候, 如下:
Paste_Image.png
此时, 用 src(i) 与 pat 的开头 pat(0) 比较, 这时,模式串前进的步数是最大的.
Paste_Image.png
但是,会漏掉一些可能匹配的串,如下:
Paste_Image.png
显然, 为了不漏掉其中任意可能匹配的case, 最大的 h 决定了模式串可以移动的最大步数.
那么怎么去求这个 h 呢?
Paste_Image.png
根据假设, 在 h 处有可能匹配的串 那么 A = C,
根据上一次的匹配结果, src[: i] = pat[:j], 则 C = D
则 A = D.
据此, h 可以定义为: 在 pat[0: j-1] 中, 分别取两个长度相等的串,一个以 pat[0] 开头, 一个以 pat[j-1] 结尾, 所有的这一对串中, 长度最大的串的长度.
对于模式串中的任意位置 j, 都可以有一个 h, 这些 h 值就构成了 next 数组了.
可以用递归的方式来求 next 数组,过程如下:
next[j] 已知, 求 next[j+1]
Paste_Image.png
比较 pat[j] 和 pat[next[j]], 这里数组序号从 0 开始.
Paste_Image.png
如果 pat[j] == pat[next[j]], 则 next[j+1] = next[j] + 1
Paste_Image.png
否则,
Paste_Image.png
需要在 A 中找 A1, 在 B 中找 B1, 使得 A1 以 pat[0] 开头, B1 以 pat[j-1]结尾, 并且 A1 == B1, 此时再去比较 pat[j] 和 pat[len(A1)], 如果 pat[j] == pat[len(A1)] 那么 next[j+1] = len(A1) + 1 , 否则继续此过程!!
那么 A1 和 B1 怎么找呢?
Paste_Image.png
根据 A = B, 则 B1 = C1, 于是 A1 = C1, 于是 A1 就是 next[ next[j] ] .
下面考虑求 next 数组中的极端情况
j = 0, 此时显然源串 和 模式串都要移动 此时 next[0] = -1, 做一个标记
j = 1, next[1] = 0
j = 2 .... (n-1) 使用上面的算法即可， 终止条件为 next < 0
program:
public static void GetNext(String pat, int[] next) {
int pat_len = pat.length();
next[0] = -1;
if (pat.length() <= 1) {
return;
}
next[1] = 0;
for (int j = 2; j < pat_len; ++j) {
next[j] = 0;
int n = next[j-1];
while (n >= 0) {
if (pat.charAt(j - 1) == pat.charAt(n)) {
next[j] = n + 1;
break;
} else {
n = next[n];
}
}
}
}
相应的 KMP 写法如下：
public static void KMP(String src, String pat) {
if (pat.length() <= 0) {
return;
}
int[] next = new int[pat.length()];
GetNext(pat, next);
int i = 0;
int j = 0;
while (i < src.length() && j < pat.length()) {
if (j < 0 || src.charAt(i) == pat.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j >= pat.length()) {
System.out.printf("found substring @ pos: %d \n", (i - pat.length()));
}
return;
}
