暴力算法

//暴力算法 int index(SString S,SString T,int pos) {int i=pos,j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else {i=i-j+2;j=1;}}if(j>T[0])return i-T[0];else return 0;}

kmp算法

next[]數組的求法：
例子：abaabcac

模式串的下標從1開始

第一位固定為0；

第二位固定為1；

從第三位（i）開始（其余的每一位都如此），
從該位 (i) 的前一位開始，從右向左尋找子串
從模式串的頭部（最左邊）,從左向右尋找子串
找到兩頭子串的最大相同的個數
把最大相同的個數的下一位的索引給next[i]

//next函數算法 void get_next(SString T,int next[]) {int j; int 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];} } int Index_KMP(SString S,SString T,int pos) { int next[MAXSTRLEN+1]; get_next(T,next);int i=pos; int j=1;while(i<=S[0]&&j<=T[0])//i j都不超過其串的長度{//失配 //1：失配，當j==0時，則目標主串的檢測指針前進一位，模式串檢測指針回到T[1].進行下一趟的比較//2：失配，當j>0時，那么在下一趟比較時，模式串的起始位置為Tnext[j],目標主串S的檢測指針不回溯，仍然指向上一趟失配的位置 if(j==0||S[i]==T[j]){++i;++j;//繼續比較后繼字符 }else j=next[j];//模式串向右移動 }if(j>T[0]) return i-T[0];//匹配成功 else return 0; }

kmp算法改進版
例子：abaabcac

求nextval[]數組：（需要根據next[]數組來求）
1.

void get_nextval(SString T,int nextval[]) {int j; int i=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;if(T[i]!=T[j])nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];} }int Index_KMP_val(SString S,SString T,int pos) { int nextval[MAXSTRLEN+1]; get_nextval(T,nextval);int i=pos; int j=1;while(i<=S[0]&&j<=T[0])//i j都不超過其串的長度{//失配 //1：失配，當j==0時，則目標主串的檢測指針前進一位，模式串檢測指針回到T[1].進行下一趟的比較//2：失配，當j>0時，那么在下一趟比較時，模式串的起始位置為Tnext[j],目標主串S的檢測指針不回溯，仍然指向上一趟失配的位置 if(j==0||S[i]==T[j]){++i;++j;//繼續比較后繼字符 }else j=nextval[j];//模式串向右移動 }if(j>T[0]) return i-T[0];//匹配成功 else return 0; }

包含三個算法的全部程序代碼

#include <stdio.h> // printf(); scanf() #include <stdlib.h> // exit() #include <malloc.h> // malloc() #include <time.h> // srand((unsigned)time(NULL)); #include <string.h>// 函數結果狀態代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2// Status是函數的類型，其值是函數結果狀態代碼 typedef int Status;// #define ElemType int // 也可以用宏定義確定ElemType類型 typedef int ElemType; // Status是函數的類型，其值是函數結果狀態代碼 -----串的定長順序存儲表示----- #define MAXSTRLEN 255 // 用戶可在255(1個字節)以內定義最大串長 typedef unsigned char SString[MAXSTRLEN + 1]; // 0號單元存放串的長度Status StrAssign(SString &T, char *chars) {if(strlen(chars) > MAXSTRLEN)return ERROR;else {T[0] = strlen(chars); // 0號單元存放串的長度for(int i=1; i<=T[0]; i++)T[i] = *(chars+i-1);return OK;} }Status StrCopy(SString &T, SString S) {for(int i=0; i<=S[0]; i++)T[i] = S[i];return OK; }int StrCompare(SString S, SString T) {int i;for(i=1; i<=S[0] && i<=T[0]; ++i)if(S[i] != T[i])return S[i]-T[i];return S[0]-T[0]; }int StrLength(SString S) {return S[0]; }Status StrEmpty(SString S) {if(S[0] == 0)return TRUE;elsereturn FALSE; }Status Concat(SString T, SString S1, SString S2) {// 若未截斷，則返回TRUE；否則返回FALSE。int i;if(S1[0]+S2[0] <= MAXSTRLEN) // 未截斷{for(i=1; i<=S1[0]; i++) // 將串S1賦給TT[i] = S1[i];for(i=1; i<=S2[0]; i++) // 將串S2賦給T中已有串S1的后面T[S1[0]+i] = S2[i];T[0] = S1[0] + S2[0]; // 新串的長度return TRUE;} else if(S1[0] < MAXSTRLEN) { // 截斷S2的部分字符序列for(i=1; i<=S1[0]; i++) // 將串S1賦給TT[i] = S1[i];for(i=1; i<=MAXSTRLEN-S1[0]; i++)// 將串S2未截斷的部分賦給T中已有串S1的后面T[S1[0]+i] = S2[i];T[0] = MAXSTRLEN;return FALSE;} else { // 截斷(僅取S1)for(i=1; i<=MAXSTRLEN; i++) // 將串S1賦給TT[i] = S1[i];T[0] = MAXSTRLEN;return FALSE;} }//Concat 算法 4.2 // 初始條件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。 // 操作結果：用Sub返回串S的第pos個字符起長度為len的子串。 Status SubString(SString Sub, SString S, int pos, int len) {int i;if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)return ERROR;for(i=1; i<=len; i++)Sub[i] = S[pos+i-1];Sub[0] = len;return OK; }void StrPrint(SString T) {for( int i = 1; i<= T[0]; i++)printf("%c ", T[i]);printf("\n"); } //將模式串的next函數值存入到數組next中 //next函數算法 void get_next(SString T,int next[]) {int j; int 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];} }//利用模式串T的next函數求T在主串S中第pos個字符之后的位置 //KMP算法 其中T非空 1<=pos<=StrLength(S) void get_nextval(SString T,int nextval[]) {int j; int i=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;if(T[i]!=T[j])nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];} }int Index_KMP(SString S,SString T,int pos) { int next[MAXSTRLEN+1]; get_next(T,next);int i=pos; int j=1;while(i<=S[0]&&j<=T[0])//i j都不超過其串的長度{//失配 //1：失配，當j==0時，則目標主串的檢測指針前進一位，模式串檢測指針回到T[1].進行下一趟的比較//2：失配，當j>0時，那么在下一趟比較時，模式串的起始位置為Tnext[j],目標主串S的檢測指針不回溯，仍然指向上一趟失配的位置 if(j==0||S[i]==T[j]){++i;++j;//繼續比較后繼字符 }else j=next[j];//模式串向右移動 }if(j>T[0]) return i-T[0];//匹配成功 else return 0; }int Index_KMP_val(SString S,SString T,int pos) { int nextval[MAXSTRLEN+1]; get_nextval(T,nextval);int i=pos; int j=1;while(i<=S[0]&&j<=T[0])//i j都不超過其串的長度{//失配 //1：失配，當j==0時，則目標主串的檢測指針前進一位，模式串檢測指針回到T[1].進行下一趟的比較//2：失配，當j>0時，那么在下一趟比較時，模式串的起始位置為Tnext[j],目標主串S的檢測指針不回溯，仍然指向上一趟失配的位置 if(j==0||S[i]==T[j]){++i;++j;//繼續比較后繼字符 }else j=nextval[j];//模式串向右移動 }if(j>T[0]) return i-T[0];//匹配成功 else return 0; }//暴力算法 int index(SString S,SString T,int pos) {int i=pos,j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else {i=i-j+2;j=1;}}if(j>T[0])return i-T[0];else return 0;} int main() { int x;int number;int pos;char c[MAXSTRLEN+1],d[MAXSTRLEN+1];SString S;SString T;printf("輸入字符串S（主串）：");scanf("%s",c);if(!StrAssign(S, c)) {printf("串長超過MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);exit(0);}printf("輸入字符串T（模式串）：");scanf("%s",c);if(!StrAssign(T, c)) {printf("串長超過MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);exit(0);} // StrPrint(S);// StrPrint(T);printf("輸入要在主串開始的位置pos：");scanf("%d",&pos);printf("選擇要是用的算法1（暴力算法）/2（kmp算法next）/3（kmp算法nextval）:");scanf("%d",&x);if(x==1){number=index(S, T, pos);printf("%d",number);}else if(x==2){int next1[MAXSTRLEN+1];get_next( T,next1);for(int i=1;i<=T[0];i++){printf("%d ",next1[i]);}printf("\n"); number=Index_KMP(S,T,pos);printf("%d",number);}else if(x==3){int nextval1[MAXSTRLEN+1];get_nextval( T,nextval1);for(int i=1;i<=T[0];i++){printf("%d ",nextval1[i]);}printf("\n"); number=Index_KMP_val(S,T,pos);printf("%d",number);}return 0;}

總結

以上是生活随笔為你收集整理的数据结构——模式匹配kmp算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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