文档介绍：KMP算法计算出当前要匹配的串T的next数组/*通过计算返回子串T的next数组*/voidget_next(StringT,int*next){ inti,j; i=1; j=0; next[1]=0; while(i<T[0])//此处T[0]表示T的长度 { if(j==0||T[i]==T[j]) { //T[i]表示后缀的单个字符,T[j]表示前缀的单个字符++i; ++j; next[i]=j; }else j=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(j>T[0]) returni-T[0]; else return0;}算法的时间复杂度:O(n+m);KMP算法改进/*求模式串T的next函数修正值并存入数组nextval*/voidget_nextval