模式匹配算法的改进——KMP算法
2006-1-5 0:00:14
★基本思想：
这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
假设主串为“s1s2,...sn",模式串为”p1p2...pn",当主串中第i个字符与模式串中第j个字符“失配”（比较不等)时，主串第i字符（i指针不回溯）应与模式中哪个字符再比较？
令当s[i]!=p[j]时，s[i]应与p[next[j]]进行比较。
例如： P="abaabcac"
★算法描述
int Index_KMP(SString S,SString T,int pos){
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。
//其中，T非空，1≤pos≤StrLength(S)。
i=pos; j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){++i;++j;}//继续比较后继字符
else j=next[j];//模式串象右移动
}
if(j>T[0])return i-T[0];//匹配成功
elsereturn 0;
}//Index_KMP
void get_next(SString T,int &next[]){
//求模式串中的next函数值并存入数组next。
i=1; next[1]=0; j=0;
while(i<T[0]){
if(j==0||T[i]==T[j]){++i; ++j; next[i]=j;}
else j=next[j];
}
}//get_next
转载