KMP模式匹配算法

东北石油大学计算机与信息技术学院李勇勇1KMP算法计算出当前要匹配的串T的next数组/*通过计算返回子串T的next数组*/voidget_next(StringT,int*next){inti,j;i=1;j=0;next[1]=0;while(iT[0])//此处T[0]表示T的长度{if(j==0||T[i]==T[j]){//T[i]表示后缀的单个字符，T[j]表示前缀的单个字符++i;++j;next[i]=j;}elsej=next[j];//如果字符不同，则j值回朔}}KMP算法/*返回子串T在主串S中第pos个字符之后的位置，如果不存在则，返回o,T非空，1=pos=StrLength(S)*/intIndex_KMP(StringS,StringT,intpos){inti=pos;//i用于主串S当前位置下标值，若pos不为1，则从pos位置处开始匹配intj=1;//j用于子串T中当前位置下标值intnext[255];//定义一next数组get_next(T,next);//对于串T做分析，得到next数组while(i=S[0]&&j=T[0])//若i小于S的长度且j小于T的长度，循环继续{if(j==0||S[i]==T[j]){//如果两个字符相等，相对于朴素算法增加了j=0的判断++i;++j;}else{//指针后退重新开始匹配j=next[j];//j退回合适的位置，i值不变}}if(jT[0])returni-T[0];东北石油大学计算机与信息技术学院李勇勇2elsereturn0;}算法的时间复杂度:O(n+m);KMP算法改进/*求模式串T的next函数修正值并存入数组nextval*/voidget_nextval(StringT,int*nextval){inti,j;i=1;j=0;nextval[1]=0;while(iT[0])//此处T[0]表示T的长度{if(j==0||T[i]==T[j]){//T[i]表示后缀的单个字符//T[j]表示前缀的单个字符++i;++j;if(T[i]!=T[j])//若当前字符与前缀字符不相同nextval[i]=j;//当前的j为nextval在i位置的值elsenextval[i]=nextval[j];//如果与前缀字符相同，则将前缀字符的nextval值赋值给nextval在i位置的值}elsej=nextval[j];//若字符不同，则j值回朔}}