一、暴力匹配

#include <iostream> using namespace std; #define MAXLEN 255 typedef struct{char ch[MAXLEN];int length; }SString; //S為主串，T為子串//暴力匹配 int Index(SString S,SString T){int i=1,j=1;int k=1;while(i<=S.length && j<=T.length){if(S.ch[i]==T.ch[j]){i++;j++;}else{ // i的第二種取值 // k++; // i=k;i=i-j+2;j=1;}}if(j>T.length)return i-T.length;elsereturn 0; }

二、KMP算法——next數組

#include <iostream> using namespace std; #define MAXLEN 255 typedef struct{char ch[MAXLEN];int length; }SString; //S為主串，T為子串//KMP-next int Index_KMP(SString S,SString T,int next[]){int i=1,j=1;while(i<=S.length&&j<=T.length){if(j==0||S.ch[i]==T.ch[j]){i++;j++;}else{j=next[j];}}if(j>T.length)return i-T.length;elsereturn 0; }

?三、nextval數組的求法

//next->nextval void get_nextval(SString T,int nextval[],int next[]){nextval[1]=0;for(int j=2;j<=T.length;j++){if(T.ch[next[j]]==T.ch[j])nextval[j]=nextval[next[j]];elsenextval[j]=next[j];} }

然后把KMP算法中的next數組替換成nextval數組即可，匹配算法不變。

總結

以上是生活随笔為你收集整理的串的模式匹配、KMP算法、nextval数组求法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。