KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
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]; else return 0; }//Index_KMPvoid get_next(SString T,int next[ ]) { //求模式串T的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新闻热点
疑难解答
