KMP算法的改进。KMP算法对朴素算法的改进，在于利用每次已得到的部分匹配:s[k+1..i]=t[1..j],但s[i+1]≠t[j+1]，j<m。它隐含着主串s中从l+1开始的子串不可能与t[1..m]匹配完全，其中l=k,k+1,…，k+j-π[j]-1（即i-π[j]-1）。因而完全匹配的测试可大步地往前推进到s中从i+1-π[j]开始的子串，而且对于它，我们已有部分匹配s[i+1-π[j]..i]= t[1..π[j]]。如果π[j]>0，为扩展这部分匹配，接着需要测试的是s[i+1]=t[π[j]+1]？但已知s[i+1]≠t[j+1]，所以，如果有t[π[j]+1] =t[j+1],那么可以肯定s中i+1-π[j]开始的子串，不可能与t[1..m]完全匹配。因而完全匹配的测试可再次推进到s中从i+1-π[π[j]]开始的子串，且我们再次有与t[1..m]的部分匹配s[i+1-π[π[j]]..i]=t[1..π[π[j]]]，如果π[π[j]]>0。接着为扩大该部分匹配，需要测试的是s[i+1]= t[π[π[j]]+1]，如果又有t[π[π[j]]+1]=t[j+1]，则完全匹配的测试还可以继续往前推进，直到t[π[π[…[π[j]]…]]+1]≠t[j+1]。
这表明对于已得到的部分匹配：
s[k+1..i]=t[1..j]，s[i+1]≠t[j+1]，j<m …………………………………（3.3.1）
如果 t[j+1]= t [π[j]+1]=…=t[π[π[…[π[j]]…]]+1]……………………（3.3.2）
e
且 π[π[…[π[j]]…]]=0
或 π[π[…[π[j]]…]]≠0但t[j+1]≠t[π[π[π[…[π[j]]…]]]+1]…(3.3.3）
e+1
那么，相应的完全匹配的测试可以直接推进到s中从i+2或i+1-π[π[π[…[π[j]]…]]]
e+1
开始的子串，且对后一种情况，该子串与t[1..m]已有部分匹配:
s[i+1-π[π[π[…[π[j]]…]]]..i] =t[1..π[π[π[…[π[j]]…]]]]
e+1 e+1
，而接着为扩大部分匹配需要做的测试是比较
s[i+1]与t[1]或s[i+1]与t[π[π[π[…[π[j]]…]]]+1]。
e+1
换句话说，在满足（3.3.1）、（3.3.2）、（3.3.3）且e≥1的情况下，完全匹配的测试允许比KMP算法有更大步的推进，即KMP算法可以作进一步的改进。
从上面的分析，我们不仅看到KMP算法可以进一步改进，而且可看出相应的改进措施：在原前缀函数π[q]的基础上，引入修改的前缀函数π’[q],q=1,2,3,…,m.
π’[π[q]] 当π[q]≠0且t[q+1]=t[π[q]+1]
π’[q]=
π[q] 当π[q]=0或t[q+1]≠t[π[q]+1]
修改后的前缀函数（Modified_Prefix_function）可实现如下：
Proc. Modified_Prefix_function（var t:string； var ppi: array[1..t.length] of integer）；
var m,q,k:integer；
pi:array[1..t.length] of integer；
begin
compute-Prefix-function(t,pi)；
m:=t.length；
for q:=1to m do
begin
k:=pi[q]；
whilek>0 and t.chs [q+1]=t.chs[k+1] do k:=pi[k]；
ppi[q]:=k
end
end；
KMP算法相应的改进只要将调用函数compute_Prefix_function改为调用函数Modified_Prefix_function，其他地方不作任何修改。
经过修改后的KMP算法，在最坏情况下的时间复杂性虽然没有明显改进，但对于那些使π’[q]<π[q]的t[1‥m]将有明显改进，而且π[q]-π’[q]越大改进越明显。例如s=’aaaabaaaaab’,t=’aaaaab’
| | 1 | 2 | 3 | 4 | 5 | 6 | | |
| π | 0 | 1 | 2 | 3 | 4 | 0 | | |
| π’ | 0 | 0 | 0 | 0 | 0 | 0 | | |
完全匹配从对s的子串s[1..6]进行测试开始，在得到部分匹配s[1..4]=t[1..4],s[5]≠t[5]，排除s[1..6]与t[1..6]完全匹配的可能之后，若按原KMP算法，要依次分别比较s[5]与t[4]，s[5]与t[3]，s[5]与t[2]，和s[5]与t[1]，依次排除s[2..7]，s[3..8]，s[4..9]和s[5..10]与t[1..6]完全匹配的可能，才能推进到测试s[6..11]与 t[1..6]的完全匹配而得到需要的结果。若按修改的KMP算法，由于4+1-π’[4]=5，马上可排除s[2..7]，…，s[4..9]与t[1..6]完全匹配的可能，将完全匹配的测试直接推进到s[5]开始的子串。发现s[5]≠t[1]后又排除s[5..10]与t[1..6]完全匹配的可能，从而推进到测试s[6..11]与t[1..6]的完全匹配，得到正确的结果。其中省却了s[5]与t[4]，s[5]与t[3]，s[5]与t[2]的比较。（注意s[5]与t[1]的比较尽管是多余的，但π’[4]=0且s[5]=t[1],按照修改后的KMP算法，还得做s[5]与t[1]的多余比较。）
结论：对KMP的改进实际上是KMP对朴素算法改进的继续，即充分利用部分匹配的信息，不仅充分利用s[k+1..i]=t[1..j]（挖掘可能隐含的匹配）而且充分利用s[i+1]≠t[j+1]（挖掘可能隐含的不匹配）。
无双 注释:
优化点:
KMP算法是对朴素算法进行隐藏匹配的优化
KMP改进算法是对KMP算法隐含不匹配的优化
void Modified_Prefix_function(vector<int>& next,const char* t)
{
// char *x, int m, int kmpNext[]) {
int t_len = strlen(t);
next.swap(vector<int>(t_len+1,0)); // 调整next数组,因为next数组从第二个元素开始使用, 长度为strlen(t)+1
int j = next[0] = -1;
for(int i =0;i < t_len; ){
// 与传统KMP算法不同就是: 如果下一个是=第一个, 那当前的值-1
// 而匹配时, 无论哪一步都会++
while ( j > -1 && t[i] != t[j] ){
printf("j[%d] > -1 && t[%d]:%c != t[%d]:%c next[%d]:%d\n",j,i,t[i],j,t[j],j,next[j]);
j = next[j];
}
i++;
j++;
next[i] = t[i] == t[j]?next[j]:j;
printf("next[%d] = %c == %c ?next[%d]:%d:%d;\n",i,t[i],t[j],j,next[j],j);
}
}
static void Modified_KMP_Matcher(const char* s,const char* t)
{
vector<int> next;
Modified_Prefix_function(next,t);
{
printf("next:\n\t");
for(int i =0;i<next.size();i++){
printf("% 2d ",next[i]);
}
printf("\n");
}
int s_len = strlen(s);
int t_len = strlen(t);
int next_idx=0;
for( int i =0; i< s_len; i++ ){
while( next_idx>-1 && s[i] != t[next_idx] )
next_idx = next[next_idx];
next_idx ++;
if( next_idx >= t_len ){
printf("Mod_KMP_Matcher:S[%s]\tT[%s] pos[%d]\n",s,t,i - t_len+1);
next_idx = next[next_idx];
}
}
}
Trackback: http://tb.donews.net/TrackBack.aspx?PostId=783999