数据结构之KMP算法实验报告武汉大学

一：实验题目：实验题4.3编写一个程序，实验顺序串的各种模式匹配运算，并在此年基础上完成如下功能：(1)建立“abcabcdabcdeabcdefabcdefg”目标串S和“abcdeabcdefab”模式串t;(2)采用简单模式匹配算法求t在s中的位置；(3)由模式串t求出next值和nextval值；(4)采用KMP算法求t在s中的位置；(5)采用改进的KMP算法求t在s中位置。二：实验项目组成：本项目由一个实验4.3.cpp文件构成。三：实验项目的程序结构：四：实验项目包含的函数的功能描述：实验4.3.cpp文件包含的函数及其功能如下：strassign(sqstring&str,charcstr[])//创建串dispstr(sqstrings)//输出串simple(sqstrings,sqstringt)getnext(sqstringt,intnext[])//模式串求next的值mainstrassigndispstrsimplegetnextkmpindexgetnextvakmpindex(sqstrings,sqstringt)//kmp算法getnextval(sqstringt,intnextval[])//得到nextval的值Main()：根据输入的字符串的字符建立目标串和模式串，调用一系列子函数实现题目的要求五：算法描述#includestdio.h#includestdlib.h#definemaxsize100typedefstruct{charch[maxsize];intlen;}sqstring;voidstrassign(sqstring&str,charcstr[])//创建串{inti;for(i=0;cstr[i]!='\0';i++)str.ch[i]=cstr[i];str.len=i;}voiddispstr(sqstrings)//输出串{inti;if(s.len0){for(i=0;is.len;i++)printf(%c,s.ch[i]);printf(\n);}}intsimple(sqstrings,sqstringt){inti=0,j=0,k;while(is.len&&jt.len){if(s.ch[i]==t.ch[j]){i++;j++;}else{i=i-j+1;//主串，子串指针回朔重新开始j=0;}}if(j=t.len)k=i-t.len;elsek=-1;returnk;}voidgetnext(sqstringt,intnext[])//模式串求next的值{intj,k;j=0;k=-1;next[0]=-1;while(jt.len-1){if(k==-1||t.ch[j]==t.ch[k]){j++;k++;next[j]=k;}elsek=next[k];}}intkmpindex(sqstrings,sqstringt)//kmp算法{intnext[maxsize],i=0,j=0,v;getnext(t,next);while(is.len&&jt.len){if(j==-1||s.ch[i]==t.ch[j]){i++;j++;}elsej=next[j];}if(j=t.len)v=i-t.len;elsev=-1;returnv;}voidgetnextval(sqstringt,intnextval[])//得到nextval的值{intj=0,k=-1;nextval[0]=-1;while(jt.len){if(k==-1||t.ch[j]==t.ch[k]){j++;k++;if(t.ch[j]!=t.ch[k])nextval[j]=k;elsenextval[j]=nextval[k];}elsek=nextval[k];}}intmain(){inti,j;intnext[maxsize],nextval[maxsize];sqstrings,t;strassign(s,abcabcdabcdeabcdefabcdefg);strassign(t,abcdeabcdefab);printf(串S:);dispstr(s);printf(串t:);dispstr(t);getnext(t,next);getnextval(t,nextval);printf(i);for(i=0;it.len;i++)printf(%4d,i);printf(\n);printf(t[i]);for(i=0;it.len;i++)printf(%4c,t.ch[i]);printf(\n);printf(next);for(i=0;it.len;i++)printf(%4d,next[i]);printf(\n);printf(nextval);for(i=0;it.len;i++)printf(%4d,nextval[i]);printf(\n);printf(kmp算法：);j=kmpindex(s,t);if(j==-1)printf(串匹配失败\n);elseprintf(t在s中的位置%d\n,j);printf(简单算法：);j=simple(s,t);if(j==-1)printf(串匹配失败\n);elseprintf(t在s中的位置%d\n,j);system(pause);}六：实验数据与实验结果:程序盘：详见源文件