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

-.z.課程設(shè)計——數(shù)據(jù)構(gòu)造設(shè)計題目：KMP算法實(shí)現(xiàn)一個模式匹配指導(dǎo)教師：徐浩學(xué)生：文莉班級：信122班**：1290842272021年6月16日問題描述：使用KMP算法實(shí)現(xiàn)一個模式匹配用C/C++編寫一個程序?qū)崿F(xiàn)模式匹配的KMP算法。要求在一個字符串中搜索*個子串，假設(shè)搜索到就返回子串的位置；假設(shè)未搜索到，就返回0。首先要輸入個主串和模式串，先根據(jù)ne*t()函數(shù)求模式串的ne*t值，利用KMP算法進(jìn)展匹配，再用輸出函數(shù)輸出結(jié)果！設(shè)計思路：該算法分為五三個模塊：第一模塊[input()函數(shù)]〔利用該函數(shù)輸入主串和模式串的值〕；第二模塊[StrLength〔〕]〔利用該函數(shù)求各串的長度〕；第三模塊[get_ne*t()函數(shù)]〔利用該函數(shù)求出模式串的ne*t函數(shù)值〕；第四模塊[Inde*_KM〔〕函數(shù)]〔利用該函數(shù)進(jìn)展主串和模式串之間的匹配〕；第五模塊[output()函數(shù)利用該函數(shù)輸出匹配結(jié)果〕。個模塊之間的調(diào)用關(guān)系如以下圖所示：圖4.1是對整個函數(shù)的流程圖。圖4.2是對KMP算法的流程圖；圖4.3是求ne*t的函數(shù)值的流程圖。因水平有限，最終程序清單與這個流程圖不同的地方，請諒解。大致思路是一致、、、數(shù)據(jù)構(gòu)造定義：*defineMA*SIZE100；intinde*_KMP(char*s,char*t,intpos);voidget_ne*t(char*t,int*);用最簡單的數(shù)組進(jìn)展KMP模式匹配主串：chars[10]="abcacbabb";模式串：chart[4]="cac";intne*t[4];intpos=0;系統(tǒng)功能介紹：求模式串的模式值ne*t[]函數(shù)用"模式匹配的KMP算法"當(dāng)主串和模式串匹配不相等是，模式串應(yīng)向右移動一段距離，此時我們需要得到模式串的ne*t函數(shù)值。如何求ne*t函數(shù)，ne*t函數(shù)值僅取決于模式本身而和主串無關(guān)。我們可以從分析ne*t函數(shù)的定義出發(fā)用遞推的方法求得ne*t函數(shù)值。由定義知：ne*t[1]=0設(shè)ne*t[j]=k，即有：＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1ne*t[j+1]="可能有兩種情況：一種情況：假設(shè)tk＝tj則說明在模式串中這就是說ne*t[j+1]=k+1，即ne*t[j＋１]=ne*t[j]+1第二種情況：假設(shè)tk≠tj則說明在模式串中t1t2…tk＂≠＂tj-k+1tj-k+2…tj＂此時可把求ne*t函數(shù)值的問題看成是一個模式匹配問題，整個模式串既是主串又是模式，而當(dāng)前在匹配的過程中，已有(4.6)式成立，則當(dāng)tk≠tj時應(yīng)將模式向右滑動，使得第ne*t[k]個字符和“主串〞中的第j個字符相比擬。假設(shè)ne*t[k]=k′，且tk′＝tj，則說明在主串中第j+1個字符之前存在一個最大長度為k′的子串，使得＂t1t2…tk′＂=＂tj-k′+1tj-k′+2…tj＂此：ne*t[j+1]=ne*t[k]+1同理假設(shè)tk′≠tj，則將模式繼續(xù)向右滑動至使第ne*t[k′]個字符和tj對齊，依此類推，直至tj和模式中的*個字符匹配成功或者不存在任何k′(1<k′<k<…<j)滿足，此時假設(shè)t1≠tj+1，則有：ne*t[j+1]=1否則假設(shè)t1=tj+1，則有：ne*t[j+1]=0綜上所述，求ne*t函數(shù)值過程的算法如下：voidget_ne*t(char*t,int*ne*t){inti=1,j=0;ne*t[0]=ne*t[1]=0;while(i<(int)StrLength(t)){if(j==0||t[i]==t[j]){i++;j++;ne*t[i]=j;}elsej=ne*t[j];}}模式匹配KMP算法的實(shí)現(xiàn)KMP算法的思想：主串s，模式t希望*趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動〞至*個位置上，使得tk對準(zhǔn)si繼續(xù)向右進(jìn)展。顯然，現(xiàn)在問題的關(guān)鍵是串t“滑動〞到哪個位置上.不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動，模式t向右“滑動〞，使tk和si對準(zhǔn)繼續(xù)向右進(jìn)展比擬，要滿足這一假設(shè)，就要有如下關(guān)系成立：＂t1t2…tk-1＂=＂si-k+1si-k+2…si-1＂(4.1)式左邊是tk前面的k-1個字符，右邊是si前面的k-1個字符。而本趟匹配失敗是在si和tj之處，已經(jīng)得到的局部匹配結(jié)果是：＂t1t2…tj-1＂=＂si-j+1si-j+2…si-1＂〔4.2〕因為k<j，所以有：＂tj-k+1tj-k+2…tj-1＂=＂si-k+1si-k+2…si-1＂(4.3)式左邊是tj前面的k-1個字符，右邊是si前面的k-1個字符，通過(4.1)和(4.3)得到關(guān)系：＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1＂(4.4)結(jié)論：*趟在si和tj匹配失敗后，如果模式串中有滿足關(guān)系(4)的子串存在，即：模式中的前k-1個字符與模式中tj字符前面的k-1個字符相等時，模式t就可以向右“滑動〞至使tk和si對準(zhǔn)，繼續(xù)向右進(jìn)展比擬即可。在求得模式的ne*t函數(shù)之后，匹配可如下進(jìn)展：假設(shè)以指針i和j分別指示主串和模式中的比擬字符，令i的初值為pos，j的初值為1。假設(shè)在匹配過程中si≠tj，則i和j分別增１，假設(shè)si≠tj匹配失敗后，則i不變，j退到ne*t[j]位置再比擬，假設(shè)相等，則指針各自增１，否則j再退到下一個ne*t值的位置，依此類推。直至以下兩種情況：一種是j退到*個ne*t值時字符比擬相等，則i和j分別增１繼續(xù)進(jìn)展匹配;另一種是j退到值為零〔即模式的第一個字符失配〕，則此時i和j也要分別增１，說明從主串的下一個字符起和模式重新開場匹配。KMP算法如下：intInde*_KMP(char*s,char*t,intpos){inti=pos,j=1;while(i<=m&&j<=n){if(j==0||s[i]==t[j-1]){i++;j++;}elsej=ne*t[j];}if(j>n)returni-n+1;elsereturn0;}程序清單：*include<stdio.h>*include<string.h>*defineMA*SIZE100intinde*_KMP(char*s,char*t,intpos);voidget_ne*t(char*t,int*);chars[10]="abcacbabb";chart[4]="cac";intne*t[4];intpos=0;intmain(){printf("主串是：\n",s);printf("模式串是：\n",t);intn;get_ne*t(t,ne*t);n=inde*_KMP(s,t,pos);printf("%d",n);return0;}intinde*_KMP(char*s,char*t,intpos){inti=pos,j=1;while(i<=(int)strlen(s)&&j<=(int)strlen(t)){if(j==0||s[i]==t[j-1]){i++;j++;}elsej=ne*t[j];}if(j>(int)strlen(t))returni-strlen(t)+1;elsereturn0;}voidget_ne*t(char*t,int*ne*t){inti=1,j=0;ne*t[0]=ne*t[1]=0;while(i<(int)strlen(t)){