KMP算法
KMP算法是一種改進的字符串匹配算法，此算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作，基本思想是，每當匹配過程中出現(xiàn)字符串比較不等時，不需回溯指針，而是利用已經(jīng)得到的“部分匹配”結果將模式向右“滑動”盡可能遠的一段距離，據(jù)徐進行比較。
定義：
① 要搜索的關鍵字符串 key K1K2......Km。
② 被搜索的源字符串 source S1S2.....Sn。
u 針對要查找的關鍵字字符串構造失效函數(shù)f(s)，該函數(shù)的功能就是在比較當Ki != Sj的時候計算出從K的第多少個字符開始重新比較。
使得K1K2...Kf(s)是最長的既是K1K2...Ks的的真前綴，又是K1K2...Ks的后綴的字串。也就是說如果我們試圖用一個文本串x匹配K1K2......Km，并且我們已經(jīng)匹配了前i個字符，但匹配Ki+1的時候失敗，也就是說x的下一個位置不是Ki+1，那么f(s)就是可能和我們當前位置為結尾的文本串匹配的最長的K1K2......Km的前綴和后綴y。也就是說文本x的下一個位置和Kf(s)比較，X當前位置之前的f(s)個字符和K1..Kf(s)是匹配的。所以直接從Kf(s)之后進行比較。
算法如下：
|
t = 0;
f(1) = 0;
for (i = 1; i < m; i++) {
while(t > 0 && (Ki+1 != Kt+1)) t = f(t);
if(Ki+1 == Kt+1) {
t = t + 1;
f(i+1) = t;
} else f(i+1) = 0;
}
|
對于串"a b a b a a"的計算f(s)的過程如下：
|
s
|
f(s)
|
當前字符串
|
說明
|
|
1
|
0
|
a
|
無真前綴
|
|
2
|
0
|
ab
|
無真前綴
|
|
3
|
1
|
aba
|
"a"是"aba"的真前綴和后綴
|
|
4
|
2
|
abab
|
"ab"是"abab"的真前綴和后綴
|
|
5
|
3
|
ababa
|
"aba"是"ababa"的真前綴和后綴
|
|
6
|
1
|
ababaa
|
"a"是"ababaa"的真前綴和后綴
|
u 針檢查S1S2.....Sn是否包含關鍵字K1K2......Km的算法。
|
s = 0;
for (i = 1; i <= n i++) { // 下標從1開始
while (s > 0 && Si != Ks+1) s = f(s);
if(Si == Ks+1) s = s + 1;
if(s == n) return "yes";
}
return "no";
|
</script>