首先，KMP最重要的是next?函數(shù)的設(shè)計(jì)，下面是next函數(shù)的原理

純手寫(xiě)，可跳過(guò)不看，網(wǎng)上有比較抽象的理論，但是比較難以理解

下面是代碼部分，重點(diǎn)在于?get_next?函數(shù)體

//KMP模式匹配算法#include<stdio.h> #include<string.h>#define SUBSTRING_LEN 50 //子串長(zhǎng)度為50int next[SUBSTRING_LEN] ;//void get_next (char *t , int next[]);int Index_KMP (char *s , char *t , int pos) ;//返回子串 t 在主串s中第pos 位置之后的數(shù)組下標(biāo)，不存在返回-1；int main (){char *s = "123456123123" ;char *t = "123" ;int index ;get_next(t,next) ;index = Index_KMP(s,t,7);printf("%d\n",index);return 0; }int Index_KMP (char *s , char *t , int pos){int s_l = strlen(s) ;int t_l = strlen(t) ;int i = pos ;int j = 0;while (i<s_l && j<t_l){if ( j==-1 || s[i]==t[j]){//如果子串不能向右繼續(xù)滑動(dòng)（j=-1），或者子串與主串在該位置上相等，則同時(shí)向右滑動(dòng)i++;j++;}else{// 子串向右滑動(dòng)，繼續(xù)與主串比較j = next[j] ;}}if (j>=t_l)return i-t_l;elsereturn -1;}void get_next (char *t , int next[]){int s_l = strlen (t) ;int i = 0 ;int j = -1 ;//相當(dāng)于子串下標(biāo)next[0]=-1;while ( i < s_l ){if ( j==-1 || t[i]==t[j] ){i++ ;j ++ ;next[i] = j ;}else{j = next[j] ;}}}
關(guān)于next數(shù)組的修正問(wèn)題，以后補(bǔ)充

總結(jié)

以上是生活随笔為你收集整理的自我理解的KMP 算法 模式匹配的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。