《实验三 串的模式匹配》由会员分享，可在线阅读，更多相关《实验三 串的模式匹配（6页珍藏版）》请在金锄头文库上搜索。
1、实验三实验三 串的模式匹配串的模式匹配一、一、 实验目的实验目的1 利用顺序结构存储串，并实现串的匹配算法。2 掌握简单模式匹配思想，熟悉 KMP 算法。二、二、 实验要求实验要求1认真理解简单模式匹配思想，高效实现简单模式匹配；2结合参考程序调试 KMP 算法，努力算法思想；3保存程序的运行结果，并结合程序进行分析。三、三、 实验内容实验内容1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；2、参考程序给出了两种不同形式的 next 数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试 KMP 算法，并与简单模式
2、匹配算法进行比较。四、程序流程图、算法及运行结果四、程序流程图、算法及运行结果3-13-1 #include#include #include#include #define#define MAXSIZEMAXSIZE 100100intint StrIndex_BF(charStrIndex_BF(char sMAXSIZE,charsMAXSIZE,char tMAXSIZE)tMAXSIZE) intint i=1,j=1;i=1,j=1;whilewhile (it0)(jt0)returnreturn (i-t0);(i-t0);elseelsereturnreturn -1;-1;
3、 intint main()main() charchar sMAXSIZE;sMAXSIZE;charchar tMAXSIZE;tMAXSIZE;intint answer,answer, i;i; printf(“Sprintf(“S StringString nn “);“);gets(s);gets(s);printf(“Tprintf(“T StringString nn “);“);gets(t);gets(t);printf(“%d“,StrIndex_BF(s,t);printf(“%d“,StrIndex_BF(s,t); /*/*验证验证*/*/if(answer=Str
4、Index_BF(s,t)=0)if(answer=StrIndex_BF(s,t)=0) printf(“n“);printf(“n“);printf(“%sn“,printf(“%sn“, s);s);forfor (i(i = = 0;0; i i #include#include #define#define MAXSIZEMAXSIZE 100100voidvoid get_nextval(unsignedget_nextval(unsigned charchar pat,intpat,int nextval)nextval) intint lengthlength = = strl
5、en(pat);strlen(pat);intint i=1;i=1;intint j=0;j=0;nextval1=0;nextval1=0;while(ip_len)if(jp_len) returnreturn i-1-p_len;i-1-p_len;elseelse returnreturn -1;-1; intint main()main() unsignedunsigned charchar textMAXSIZE;textMAXSIZE;unsignedunsigned charchar patMAXSIZE;patMAXSIZE;intint nextvalMAXSIZE;ne
6、xtvalMAXSIZE;intint answer,answer, i;i; printf(“nBoyer-Mooreprintf(“nBoyer-Moore StringString SearchingSearching Program“);Program“);printf(“n=“);printf(“n=“);printf(“nnTextprintf(“nnText StringString “);“);gets(text);gets(text);printf(printf( “nPattern“nPattern StringString “);“);gets(pat);gets(pat
7、);get_nextval(pat,nextval);get_nextval(pat,nextval);if(answer=Index_KMP(text,if(answer=Index_KMP(text, pat,nextval)=0)pat,nextval)=0) printf(“n“);printf(“n“);printf(“%sn“,printf(“%sn“, text);text);forfor (i(i = = 0;0; i i =1(j=1 nextj;i+;i+; j+;j+;if(ti=tj)if(ti=tj) nextinexti = = nextj;nextj; elsee
8、lse nextinexti = = j;j; voidvoid main()main() charchar *p=“abcaababc“;*p=“abcaababc“;intint i,str10;i,str10;GetNext1(p,str);GetNext1(p,str);printf(“Putprintf(“Put out:n“);out:n“);for(i=1;i10;i+)for(i=1;i10;i+)printf(“%d“,stri);printf(“%d“,stri);GetNext2(p,str);GetNext2(p,str);printf(“n“);printf(“n“);for(i=1;i10;i+)for(i=1;i10;i+)printf(“%d“,stri);printf(“%d“,stri);printf(“n“);printf(“n“);getch();getch();
