4.3.2 串的模式匹配的改进算法

　　上页中第二个动画演示的匹配过程正是本节要讨论的模式匹配的改进算法，它是由三位计算机学者 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发现的，因此人们通常简称它为 KMP 算法。可以证明它的时间复杂度为O(m+n)，直观地看，是因为在匹配过程中指针 i 没有回溯。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。

　　回顾上页所举实例，假设主串为 ，模式串为 ，当 时，按简单算法接着应进行 和 的比较，由于我们在这之前的匹配过程中已经得到了 "=" 的信息，而从模式串本身又得到了 "" 的信息，由此可得结论：，也就没有必要进行 和 的比较，而直接进行 和 的比较。同理当 时，只要直接进行 和 的比较即可。换句话说，在进行了 和 的比较并且知道两者不等之后，可将T串直接向右滑动到和 对齐的起始位置进行下一轮的匹配，这是由于T串本身的特性和之前的匹配过程决定的。

　　一般情况下，若 " ..."=" ..."，并且不可能存在 k'>k 满足此式，又从匹配过程中得到 " ..."=" ..." 和 '' ''，这就是说，从前面的匹配过程已经得到结果 " ..."=" ..." 并且不可能存在 k'>k 满足此式，那么下一步只需要继续进行 '' 和 '' 的比较即可。称"k"为模式串中字符 '' 的 next 函数值。
　

 
　　从上页同样一个实例的两个匹配过程可见，简单算法之所以时间复杂度会在最坏情况下达到"二次级" 是因为，当进行"两个子串的比较"过程中，不管是 T 串的第几个字符发生"不等"的情况，指针 i 都必须 "回溯" 到S串中原来开始进行比较的字符的下一个位置。而在第二个匹配过程中，当发生两个串中字符比较不等时指针 i 不需要回溯，而只要将 T 串向右滑动到一定位置继续进行字符间的比较。如上例中，S串中除了第3、7和10个字符和T串中的字符比较了两次之外，其它字符和T串中的字符均只进行了一次比较。

 思考题 你知道是因为什么原因吗？
　
 
 　定义：
　　

　　例如，下列所示为模式串的 next 函数值的两个例子。

j
0
1
2
3
4
模式串
a
b
c
a
c
next[j]
-1
0
0
0
1

j
0
1
2
3
4
5
6
7
8
模式串
a
b
a
b
c
a
a
b
c
next[j]
-1
0
0
1
2
0
1
1
2
　		  　　next 函数值的含义是：当出现 时，下一次的比较应该在 和 之间进行。 
 
算法 算法 4.8
　　int Index_KMP(char S[], char T[], int pos)
　{
　　// 利用模式串T的next函数求T在主串S中第pos个字符之后第一次
　　// 出现的位置的KMP算法。其中1≤pos≤StrLength(S)
　　i = pos-1; j = 0;
　　while ( S[i] != '\0' && T[j] != '\0' )
　　　if (j = = -1 || S[i] = = T[j])
　　　　{ ++i; ++j; } 　　　　　　　　　// 继续比较后继字符
　　　else j = next[j]; 　　　　　　　　// 模式串向右移动
　　}//while
　　if ( T[j] == '\0' ) return (i-j); 　　// 匹配成功
　　else return 0;
　} 　　　　　　　　　　　　　　　　　// Index_KMP
 　　仔细比较算法4.8和4.7，你一定会发现这两个算法只有两个地方不同，一是当 S[i]T[j] 时，在算法4.7中指针 i 回溯到 i-j+1 的位置，指针 j 重又指向第 1 个字符，而在算法4.8中，指针i不变，而指针 j=next[j]；二是 if 语句的条件中多了一种情况(j==-1)，那么这是一种什么情况呢？

　　从 next 函数值的定义看，next[0]=-1，因此while 循环中出现j=-1的情况，只能是在 S[i]T[0] 之后，即T串中的第一个字符和S串中某个字符比较不等，显然，此时应将T串向右滑动。