实验四模式匹配

实验四模式匹配一、实验目的和要求掌握字符串存储结构的描述，学会字符串的模式匹配算法的应用。二、实验内容和原理C语言结构化程序设计思想，结构体及指针和字符数组的应用。三、主要仪器设备装有VisualC++/TurboC++等C程序编译软件的计算机。四、实验中程序的源码1.朴素模式匹配算法程序代码如下：#includestdio.h#includestring.h#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;intindex(seqstringp,seqstringt){inti,j,succ;i=0;succ=0;while((i=t.length-p.length)&&(!succ)){j=0;succ=1;while((j=p.length-1)&&succ)if(p.str[j]==t.str[i+j])j++;elsesucc=0;++i;}if(succ)return(i-1);elsereturn(-1);}voidmain(){seqstringt,p;intpos;scanf(%s,t.str);t.length=strlen(t.str);scanf(%s,p.str);p.length=strlen(p.str);pos=index(p,t);printf(\n);if(pos==-1)printf(nofound);elseprintf(thepositionis%d,pos+1);}这里写出程序源代码，见书76页算法4.102.快速模式匹配算法程序代码如下：#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;voidgetnext(seqstringp,intnext[]){inti,j;next[0]=-1;i=0;j=-1;while(ip.length){if(j==-1||p.str[i]==p.str[j]){++i;++j;next[i]=j;}elsej=next[j];}for(i=0;ip.length;i++)printf(%d,next[i]);}voidmain(){seqstringp;intnext[50];scanf(%s,p.str);p.length=strlen(p.str);getnext(p,next);}这里写出程序源代码，见书78页算法4.11和79页算法4.12五、实验结果与分析1.这里写出第一个程序的结果与分析，见书75页基本思想2.这里写出第二个程序的结果与分析，见书78页基本思想