3.KMP算法（Knuth-Morris-Pratt ）
该算法的与Rabin-Karp一脉相承。也就是先排除可能不是的，在可能中逐一比较。
I.π函数的得到：
COMPUTE-PREFIX-FUNCTION(P) 1 m ← length[P] 2 π[1] ← 0 3 k ← 0 4 for q ← 2 to m 5 do while k > 0 and P[k + 1] ≠ P[q] 6 do k ← π[k] 7 if P[k + 1] = P[q] 8 then k ← k + 1 9 π[q] ← k 10 return π II.伪代码算法: KMP-MATCHER(T, P) 1 n ← length[T] 2 m ← length[P] 3 π ← COMPUTE-PREFIX-FUNCTION(P) 4 q ← 0 ▹Number of characters matched. 5 for i ← 1 to n ▹Scan the text from left to right. 6 do while q > 0 and P[q + 1] ≠ T[i] 7 do q ← π[q] ▹Next character does not match. 8 if P[q + 1] = T[i] 9 then q ← q + 1 ▹Next character matches. 10 if q = m ▹Is all of P matched? 11 then print "Pattern occurs with shift" i - m 12 q ← π[q] ▹Look for the next match. C语言算法实现： void COMPUTE_PREFIX_FUNCTION(char *P, char *PI) { /*---------------------------------------------------------------*/ /* Local Variables */ /*---------------------------------------------------------------*/ int m = 0; int k =0,q =0; DWORD begin,end; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ begin = GetTickCount(); assert(P); assert(PI); m = strlen(P); PI[0] = 0; for(q=1;q<m;q++) { while((k>0 )&& (P[k]!=P[q])) { k = PI[k]; } if(P[k]==P[q]) { k = k+1; } PI[q] = k; } end = GetTickCount(); printf("the time is %d ms/n",end-begin); } /********************************************************************** *[in] T string *[in] P key * ***********************************************************************/ void mmi_KMP_string_match(char* T, char* P) { /*----------------------------------------------------------------*/ /* Local Variables */ /*-------------------------------------------------------------*/ int m,n = 0; int k =0,q,i =0; char PI[20] = {0}; DWORD begin,end; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ begin = GetTickCount(); n = strlen(T); m = strlen(P); COMPUTE_PREFIX_FUNCTION(P,PI); q =0; for(i =0;i<n;i++) { while((q>0)&&(P[q]!=T[i])) { q = PI[q]; } if(P[q] ==T[i]) { q =q+1; } if(q==m) { printf("Pattern occurs here, %d!/n",i-m+1); q = PI[q]; } } end = GetTickCount(); DWORD count = end - begin; printf("the time is %d ms in KMP/n",begin); printf("the time is %d ms in KMP/n",end); printf("the time is %d ms in KMP/n",count); }