使用KMP算法實(shí)現(xiàn)一個(gè)模式匹配

1、 課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)題目：KMP算法實(shí)現(xiàn)一個(gè)模式匹配 指導(dǎo)老師：徐浩 學(xué)生： 文莉 班級(jí) ： 信122班 學(xué)號(hào) ：129084227 2014年6月16日1、 問(wèn)題描述：使用KMP算法實(shí)現(xiàn)一個(gè)模式匹配用C/C+編寫(xiě)一個(gè)程序?qū)崿F(xiàn)模式匹配的KMP算法。要求在一個(gè)字符串中搜索某個(gè)子串，若搜索到就返回子串的位置；若未搜索到，就返回0。 首先要輸入個(gè)主串和模式串，先根據(jù)next( )函數(shù)求模式串的next值，利用KMP 算法進(jìn)行匹配，再用輸出函數(shù)輸出結(jié)果！2、 設(shè)計(jì)思路：該算法分為五三個(gè)模塊：第一模塊input( )函數(shù)（利用該函數(shù)輸入主串和模式串的值）；第二模塊StrLength（）（利用該函數(shù)求

2、各串的長(zhǎng)度）；第三模塊get_next( )函數(shù)（利用該函數(shù)求出模式串的next函數(shù)值）；第四模塊Index_KM（）函數(shù)（利用該函數(shù)進(jìn)行主串和模式串之間的匹配）； 第五模塊output( )函數(shù)利用該函數(shù)輸出匹配結(jié)果）。個(gè)模塊之間的調(diào)用關(guān)系如下圖所示：圖4.1是對(duì)整個(gè)函數(shù)的流程圖。圖4.2是對(duì)KMP算法的流程圖；圖4.3是求next的函數(shù)值的流程圖。因水平有限，最終程序清單與這個(gè)流程圖不同的地方，請(qǐng)諒解。大致思路是一致、3、 數(shù)據(jù)結(jié)構(gòu)定義：#define MAXSIZE 100；int index_KMP(char *s,char *t,int pos); void get_next(cha

3、r *t,int *); 用最簡(jiǎn)單的數(shù)組進(jìn)行KMP模式匹配主串：char s10="abcacbabb" 模式串：char t4="cac" int next4; int pos=0; 4、 系統(tǒng)功能介紹：求模式串的模式值next函數(shù)用模式匹配的KMP算法當(dāng)主串和模式串匹配不相等是，模式串應(yīng)向右移動(dòng)一段距離，此時(shí)我們需要得到模式串的next函數(shù)值。 如何求next函數(shù)，next函數(shù)值僅取決于模式本身而和主串無(wú)關(guān)。我們可以從分析next函數(shù)的定義出發(fā)用遞推的方法求得next函數(shù)值。由定義知：next1=0設(shè)nextj=k，即有：t1 t2 tk-1 =tj

4、-k+1 tj-k+2 tj-1 nextj+1=?可能有兩種情況：一種情況：若tk tj 則表明在模式串中這就是說(shuō)nextj+1=k+1，即nextj=nextj+1 第二種情況：若tk tj 則表明在模式串中t1 t2 tk tj-k+1 tj-k+2 tj 此時(shí)可把求next函數(shù)值的問(wèn)題看成是一個(gè)模式匹配問(wèn)題，整個(gè)模式串既是主串又是模式，而當(dāng)前在匹配的過(guò)程中，已有(4.6)式成立，則當(dāng)tk tj 時(shí)應(yīng)將模式向右滑動(dòng)，使得第nextk個(gè)字符和“主串”中的第j個(gè)字符相比較。若nextk=k，且t ktj，則說(shuō)明在主串中第j+1個(gè)字符之前存在一個(gè)最大長(zhǎng)度為k的子串，使得t1 t2 t k =t

5、j-k+1 tj- k+2 tj 此： nextj+1=nextk+1 同理若t ktj，則將模式繼續(xù)向右滑動(dòng)至使第nextk個(gè)字符和tj 對(duì)齊，依此類推，直至tj 和模式中的某個(gè)字符匹配成功或者不存在任何 k(1< k<k <<j)滿足，此時(shí)若t1tj+1 ， 則有：nextj+1=1 否則若t1=tj+1 ，則有：nextj+1=0 綜上所述，求next函數(shù)值過(guò)程的算法如下： void get_next(char *t,int *next) int i=1,j=0; next0=next1=0; while (i<(int)StrLength(t) if (j

6、=0|ti=tj) i+; j+; nexti=j; else j=nextj; 模式匹配KMP算法的實(shí)現(xiàn)KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動(dòng)”至某個(gè)位置上，使得tk 對(duì)準(zhǔn) s i 繼續(xù)向右進(jìn)行。顯然，現(xiàn)在問(wèn)題的關(guān)鍵是串t“滑動(dòng)”到哪個(gè)位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動(dòng)，模式t向右“滑動(dòng)”，使tk和si對(duì)準(zhǔn)繼續(xù)向右進(jìn)行比較，要滿足這一假設(shè)，就要有如下關(guān)系成立：t1 t2 tk-1 =si-k+1 si-k+2 si-1 (4.1)式左邊是tk前面的k-1個(gè)字符，右邊是si 前面的k-1個(gè)字符。而本趟匹配失敗是在s

7、i和tj之處，已經(jīng)得到的部分匹配結(jié)果是：t1 t2 tj-1 =si-j+1 si-j+2 si-1 （4.2）因?yàn)閗<j，所以有：tj-k+1 tj-k+2 tj-1 =si-k+1 si-k+2 si-1 (4.3)式左邊是 tj前面的k-1個(gè)字符，右邊是si 前面的k-1個(gè)字符，通過(guò)(4.1)和(4.3)得到關(guān)系：t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 (4.4)結(jié)論：某趟在si和tj匹配失敗后，如果模式串中有滿足關(guān)系(4)的子串存在，即：模式中的前k-1個(gè)字符與模式中tj字符前面的k-1個(gè)字符相等時(shí)，模式t就可以向右“滑動(dòng)”至使tk和si對(duì)準(zhǔn)，繼續(xù)向右進(jìn)行比

8、較即可。在求得模式的next函數(shù)之后，匹配可如下進(jìn)行：假設(shè)以指針i和j分別指示主串和模式中的比較字符，令i的初值為pos，j的初值為1。若在匹配過(guò)程中sitj，則i和j分別增，若sitj 匹配失敗后，則i不變，j退到nextj位置再比較，若相等，則指針各自增，否則j再退到下一個(gè)next值的位置，依此類推。直至下列兩種情況：一種是j退到某個(gè)next值時(shí)字符比較相等，則i和j分別增繼續(xù)進(jìn)行匹配; 另一種是j退到值為零（即模式的第一個(gè)字符失配），則此時(shí)i和j也要分別增，表明從主串的下一個(gè)字符起和模式重新開(kāi)始匹配。KMP算法如下：int Index_KMP(char *s,char *t,int po

9、s) int i=pos,j=1; while (i<=m&&j<=n) if (j=0|si=tj-1) i+; j+; else j=nextj; if (j>n) return i-n+1; else return 0; 5、 程序清單：#include <stdio.h> #include <string.h> #define MAXSIZE 100int index_KMP(char *s,char *t,int pos); void get_next(char *t,int *); char s10="abcacb

10、abb" char t4="cac" int next4; int pos=0; int main() printf ("主串是：n",s); printf("模式串是：n",t); int n; get_next(t,next); n=index_KMP(s,t,pos); printf("%d",n); return 0; int index_KMP(char *s,char *t,int pos) int i=pos,j=1; while (i<=(int)strlen(s)&&j<=(int)strlen(t) if (j=0|si=tj-1) i+; j+; else j=nextj; if (j>(int)strlen(t) return i-strlen(t)+1; else return 0; void get_next(char *t,in