KMP算法

KMP算法

kmp算法是一種改進的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫裡斯——普拉特操作簡稱KMP算法）。KMP算法的關鍵是根據給定的模式串W1,m,定義一個next函數。next函數包含了模式串本身局部匹配的信息。

next數組的長度就是T串的長度，有如下定義：

當j=0時，next[j]=-1；

當j>0時，next[j]=MAX{k|0<k<j，且‘T₀...T_k-2’=‘T_j-k...T_j-1’}當此集合不為空；

其它情況，next[j]=0，其它情況

字符串和待匹配字符串都是從0開始計算的，和有的書上講的從1開始是不同的。

樸素匹配算法：當比較幾個1---n)字符後，可能第一次比較就不相等，可能中間不相等，也可能最後一個不相等，但是都會退回到上次開始比較的後一個從新開始比較。

KMP算法：是不會退回比較的，一直向前。

代碼如下：

#include <stdio.h>
void get_next(const char *T, int next[],int T_len)
{
int i = 0;
int j = -1;
next[0] = -1;
while(i<T_len - 1)
{
if(j == -1 || T[i] == T[j])
{
++i;
++j;
//  next[i] = j;  //沒有改進的算法
if(T[i] != T[j])    //改進的算法
next[i] = j;
else
next[i] = next[j];
}
else
{
j = next[j];
}
}
}
int Index_KMP(const char *S, const char *T, int pos)
{
int next[255];
int i = pos;
int j = 0;
int T_length = 0;
while(T[T_length]!='\0')
{
T_length++;
}
get_next(T,next,T_length);
while(S[i]!='\0' && j!=T_length)
{
if(j == -1  || S[i] == T[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if(j == T_length)
return i-T_length;
else
return -1;
}
int main()
{
char *S = "abcacaabaaaecdeaaaabacdeabcd";
char *T = "aaaa";
printf("%d\n",Index_KMP(S,T,0));
return 0;
}

改進的KMP算法，它是在計算出next值的同時，如果a位字符與它next值指向的b位字符相等，則該a位的nextval就指向b位的next_val值，如果不等，則該a位的nextval值就是它自己a位的next值。

本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1296748