當(dāng)源字符串 src 和 模式串 pat 不匹配的時(shí)候, 如下:
Paste_Image.png
此時(shí), 用 src(i) 與 pat 的開(kāi)頭 pat(0) 比較, 這時(shí),模式串前進(jìn)的步數(shù)是最大的.
Paste_Image.png
但是,會(huì)漏掉一些可能匹配的串,如下:
Paste_Image.png
顯然, 為了不漏掉其中任意可能匹配的case, 最大的 h 決定了模式串可以移動(dòng)的最大步數(shù).
那么怎么去求這個(gè) h 呢?
Paste_Image.png
根據(jù)假設(shè), 在 h 處有可能匹配的串 那么 A = C,
根據(jù)上一次的匹配結(jié)果, src[: i] = pat[:j], 則 C = D
則 A = D.
據(jù)此, h 可以定義為: 在 pat[0: j-1] 中, 分別取兩個(gè)長(zhǎng)度相等的串,一個(gè)以 pat[0] 開(kāi)頭, 一個(gè)以 pat[j-1] 結(jié)尾, 所有的這一對(duì)串中, 長(zhǎng)度最大的串的長(zhǎng)度.
對(duì)于模式串中的任意位置 j, 都可以有一個(gè) h, 這些 h 值就構(gòu)成了 next 數(shù)組了.
可以用遞歸的方式來(lái)求 next 數(shù)組,過(guò)程如下:
next[j] 已知, 求 next[j+1]
Paste_Image.png
比較 pat[j] 和 pat[next[j]], 這里數(shù)組序號(hào)從 0 開(kāi)始.
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] 開(kāi)頭, B1 以 pat[j-1]結(jié)尾, 并且 A1 == B1, 此時(shí)再去比較 pat[j] 和 pat[len(A1)], 如果 pat[j] == pat[len(A1)] 那么 next[j+1] = len(A1) + 1 , 否則繼續(xù)此過(guò)程!!
那么 A1 和 B1 怎么找呢?
Paste_Image.png
根據(jù) A = B, 則 B1 = C1, 于是 A1 = C1, 于是 A1 就是 next[ next[j] ] .
下面考慮求 next 數(shù)組中的極端情況
j = 0, 此時(shí)顯然源串 和 模式串都要移動(dòng) 此時(shí) next[0] = -1, 做一個(gè)標(biāo)記
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];
}
}
}
}
相應(yīng)的 KMP 寫(xiě)法如下：
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;
}
