实验三-串的模式匹配.doc

《实验三-串的模式匹配.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三串的模式匹配一、实验目的1．利用顺序结构存储串，并实现串的匹配算法。2．掌握简单模式匹配思想，熟悉KMP算法。二、实验要求1．认真理解简单模式匹配思想，高效实现简单模式匹配；2．结合参考程序调试KMP算法，努力算法思想；3．保存程序的运行结果，并结合程序进行分析。三、实验内容1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并

2、与简单模式匹配算法进行比较。四、程序流程图、算法及运行结果3-1#include#include#defineMAXSIZE100intStrIndex_BF(chars[MAXSIZE],chart[MAXSIZE]){inti=1,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]);elsereturn-1;}intmain(){ch

3、ars[MAXSIZE];chart[MAXSIZE];intanswer,i;printf("SString-->");gets(s);printf("TString-->");gets(t);printf("%d",StrIndex_BF(s,t));/*验证*/if((answer=StrIndex_BF(s,t))>=0){printf("");printf("%s",s);for(i=0;i

4、nPatternFoundatlocation:%d",answer);}elseprintf("PatternNOTFOUND.");getch();return0;}3-2#include#include#defineMAXSIZE100voidget_nextval(unsignedcharpat[],intnextval[]){intlength=strlen(pat);inti=1;intj=0;nextval[1]=0;while(i

5、if(j==0

6、

7、pat[i-1]==pat[j-1]){++i;++j;if(pat[i-1]!=pat[j-1])nextval[i]=j;elsenextval[i]=nextval[j];}elsej=nextval[j];}}intIndex_KMP(unsignedchartext[],unsignedcharpat[],intnextval[]){inti=1;intj=1;intt_len=strlen(text);intp_len=strlen(pat);while(i<=t_len&&j<=p

8、_len){if(j==0

9、

10、text[i-1]==pat[j-1]){++i;++j;}elsej=nextval[j];}if(j>p_len)returni-1-p_len;elsereturn-1;}intmain(){unsignedchartext[MAXSIZE];unsignedcharpat[MAXSIZE];intnextval[MAXSIZE];intanswer,i;printf("Boyer-MooreStringSearchingProgram");printf("======

11、==============================");printf("TextString-->");gets(text);printf("PatternString-->");gets(pat);get_nextval(pat,nextval);if((answer=Index_KMP(text,pat,nextval))>=0){printf("");printf("%s",text);for(i=0;i

12、t);printf("PatternFoundatlocation%d",answer);}elseprintf("PatternNOTFOUND.");getch();return0;}3-3#include"stdio.h"voidGetNext1(char*t,intnext[]){inti=1,j=0;next[1]=0;while(i<=9)