实验三 串的模式匹配.doc

实验三 串的模式匹配一、 实验目的1 利用顺序结构存储串，并实现串的匹配算法。2 掌握简单模式匹配思想，熟悉KMP算法。二、 实验要求1认真理解简单模式匹配思想，高效实现简单模式匹配；2结合参考程序调试KMP算法，努力算法思想；3保存程序的运行结果，并结合程序进行分析。三、 实验内容1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。四、程序流程图、算法及运行结果3-1#include #include #define MAXSIZE 100int StrIndex_BF(char sMAXSIZE,char tMAXSIZE) int i=1,j=1; while (i=s0 & jt0) return (i-t0); else return -1;int main() char sMAXSIZE; char tMAXSIZE; int answer, i; printf(S String -n ); gets(s); printf(T String -n ); gets(t); printf(%d,StrIndex_BF(s,t); /*验证*/ if(answer=StrIndex_BF(s,t)=0) printf(n); printf(%sn, s); for (i = 0; i answer; i+) printf( ); printf(%s, t); printf(nnPattern Found at location:%dn, answer); else printf(nPattern NOT FOUND.n); getch(); return 0;3-2#include #include #define MAXSIZE 100void get_nextval(unsigned char pat,int nextval) int length = strlen(pat); int i=1; int j=0; nextval1=0; while(ilength) if(j=0|pati-1=patj-1) +i; +j; if(pati-1!=patj-1) nextvali=j; else nextvali=nextvalj; else j=nextvalj; int Index_KMP(unsigned char text, unsigned char pat,int nextval) int i=1; int j=1; int t_len = strlen(text); int p_len = strlen(pat); while(i=t_len&jp_len) return i-1-p_len; else return -1; int main() unsigned char textMAXSIZE; unsigned char patMAXSIZE; int nextvalMAXSIZE; int answer, i; printf(nBoyer-Moore String Searching Program); printf(n=); printf(nnText String - ); gets(text); printf( nPattern String - ); gets(pat); get_nextval(pat,nextval); if(answer=Index_KMP(text, pat,nextval)=0) printf(n); printf(%sn, text); for (i = 0; i answer; i+) printf( ); printf(%s, pat); printf(nnPattern Found at location %dn, answer); else printf(nPattern NOT FOUND.n); getch(); return 0;3-3#include stdio.hvoid GetNext1(char *t,int next) int i=1,j=0; next1=0; while(i=9) if(j=0|ti=tj) +i; +j; nexti=j; else j=nextj; void GetNext2(char *t , int next) int i=1, j = 0; next1= 0; while (i=1 & ti != tj ) j = nextj; i+; j+; if(ti=tj) nexti = nextj; else nexti = j; void main() char *p=abcaababc; int i,str10; GetNext1(p,str); printf(Put out:n); for