KMP算法与一个经典概率问题

s(i-j+1)……s(i-1)’ 由于

s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j), ‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’ 即： 主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i)

…………. || (相配) || || ?(有待比较) 匹配串： P(1) p(2) ……..... p(k-1) p(k) 现在我们把前面总结的关系综合一下 有： S(1)…s(i-j +1)… s(i-k +1) s(i-k +2)

…… s(i-1) s(i) …… || (相配) || || || ≠(失配) P(1) ……p(j-k+1) p(j-k+2) …...... p(j-1) p(j) || (相配) || || ?(有待比较) P(1) p(2) ……...... p(k-1) p(k) 由上，我们得到关系： 'p(1) p(2) p(3)…..p(k-1)’ = ' p(j-k+1)p(j-k+2)……p(j-1)’ 接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码) K 是和next有关系的，不过在最初看的时候，你不要太追究k

到底是多少，至于next值是怎么求出来的，我教你怎么学会。 课本83页不是有个例子吗？就是 图4.6 你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。 在理解上面代码的基础上，建议自己寻找一些KMP算法的练习，也可以自己写两个较为简单的字符串进行人脑模拟这种方法的练习，以加深对算法的理解。

KMP算法的优化

KMP算法是可以被进一步优化的。 我们以一个例子来说明。譬如我们给的P字符串是

“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i 0 1 2 3 4 5 6 7 8 9

p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1

但是，如果此时发现p(i) == p(k)，那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 优化的next[i] -1 0 0 0 -1 1 0 0 3 0

附： KMP算法查找串S中含串P的个数count

#include <iostream> #include <stdlib.h> #include <vector> using namespace std; inline void NEXT(const string&

T,vector<int>& next) { //按模式串生成vector,next(T.size()) next[0]=-1; for(int i=1;i<T.size();i++ ){ int j=next[i-1];

while(T[i]!=T[j+1]&& j>=0 ) j=next[j] ; //递推计算 if(T[i]==T[j+1])next[i]=j+1; else next[i]=0; // } } inline string::size_type

COUNT_KMP(const string& S, const string& T) { //利用模式串T的next函数求T在主串S中的个数count的KMP算法 //其中T非空， vector<int> next(T.size()); NEXT(T,next); string::size_type index,count=0;

for(index=0;index<S.size();++index){ int pos=0; string::size_type iter=index; while(pos<T.size() &&

iter<S.size()){ if(S[iter]==T[pos]){ ++iter;++pos; } else{ if(pos==0)++iter; else pos=next[pos-1]+1; } }//while end

if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count; } int main(int

argc, char *argv[]) { string

S=\ string T=\ string::size_type count=COUNT_KMP(S,T);

cout<<count<<endl; system(\ return 0; } 补上个Pascal的KMP算法源码 PROGRAM Impl_KMP; USES CRT; CONST MAX_STRLEN = 255; VAR next : array [ 1 .. MAX_STRLEN ] of integer; str_s, str_t : string; int_i : integer; Procedure get_nexst( t : string ); Var j, k : integer; Begin j := 1; k := 0; while j < Length(t) do begin if ( k = 0 ) or ( t[j] = t[k] ) then begin j := j + 1; k := k + 1; next[j] := k; end else k := next[k]; end; End; Function index( s : string; t : string ) : integer; Var i, j : integer; Begin get_next(t); index := 0; i := 1; j := 1; while ( i <= Length(s) ) and ( j <= Length(t) ) do begin if ( j = 0 ) or ( s[i]= t[j] ) then begin i := i + 1; j := j + 1; end else j := next[j]; if j > Length(t) then index := i - Length(t); end; End; BEGIN ClrScr;{清屏，可不要} Write(‘s = ’);