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新聞熱點
疑難解答
