KMP算法
KMP算法是一种改进的字符串匹配算法，此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作，基本思想是，每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离，据徐进行比较。
定义：
① 要搜索的关键字符串 key K1K2......Km。
② 被搜索的源字符串 source S1S2.....Sn。
u 针对要查找的关键字字符串构造失效函数f(s)，该函数的功能就是在比较当Ki != Sj的时候计算出从K的第多少个字符开始重新比较。
使得K1K2...Kf(s)是最长的既是K1K2...Ks的的真前缀，又是K1K2...Ks的后缀的字串。也就是说如果我们试图用一个文本串x匹配K1K2......Km，并且我们已经匹配了前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>