实验6 串的模式匹配

1、实验六串的模式匹配.实验目的(1)利用顺序结构存储串，并实现串的匹配算法。掌握简单模式匹配思想、熟悉KMP算法。.实验内容(1)用键盘输入初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置。设计并调试KMP算法，并与简单模式匹配算法进行比较。.实验要求(1)根据实验内容编写程序，上机调试并获得运行结果(2)撰写实验报告.关键操作思路与算法本次实验将会使用两种方法进行模式匹配，分别是简单的模式匹配算法和更加快速的模式匹配算法(KMP算法)。定义串结构并创建串这里定义串使用线性结构创建，串结构包含data数组与长度len，创建串时首先输入串的长度，

2、再依次根据长度来输入串的内容，这里用到了新知识fflush(stdin)函数，这个函数的作用是清除缓存区，因为每次输入之后都会按一次空格，如果不加这个或者是加getchar()那个空格字符就会被下一次的scanf()所接受typedefstructdatatypedataMAXNUM;intlen;SString；/创建一个串voidSStringCreate(SString*t)inti,j;charc;printf(请输入串的长度：”)；scanf(%d,&j);t-len=j;for(i=0;ilen;i+)printf(请输入第4个字符：，(i+1);fflush(stdin);sca

3、nf(%c,&c);t-datai=c; .5.源代码#include#include#include#include#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR-1#defineINFEASIBLE-1#defineMAXNUM100typedefintdatatype;typedefstructdatatypedataMAXNUM;intlen;String;建立串voidStringCreate(String*s)inti,j;charc;printf(请输入字符串长度：”)

4、；scanf(%d,&j);for(i=0;idatai=c;s-datai=0;38.39.s-len=j;/输出串voidStringPrint(String*s)TOC o 1-5 h zinti;for(i=0;ilen;i+)printf(%c”,s-datai);printf(n);判断是否为空字符串intStringIsEmpty(String*s)if(s-len=0)TOC o 1-5 h zreturnTRUE;elsereturnERROR;求字符串长度intStringLenth(String*s)printf(字符串长度为:%dn,s-len);return(s-le

5、n);复制串voidStringCopy(String*s,String*t)将串t的值复制到串s中74.inti;75.for(i=0;ilen;i+)76.77.s-datai=t-datai;s-len=t-len;串比较intStringCompare(String*s,String*t)若串s=t，则返回0;若st,则返回正数，若st,则返回负数127.127.TOC o 1-5 h zinti;for(i=0;ilen&ilen;i+)if(s-datai!=t-datai)return(s-datai-t-datai);return(s-len-t-len);/串连接intStr

6、ingconcat(String*s,String*t)/将串t连接到串s的后面97.inti,flag;98.if(s-len+t-lenlen;ilen+t-len;i+)101.102.s-datai=t-datai-s-len;103.104.s-len+=t-len;105.flag=TRUE;106.107.else108.109.if(s-lenlen;idatai=t-datai-s-len;114.115.s-len=MAXNUM;116.flag=FALSE;117.118.else串s的长度等于MAXNUM,串t不能被连接119.120.flag=0;121.122.12

7、3.returnflag;/插入串intStringInsert(String*s,intpos,String*t)128.inti;129.if(poss-len)/130.131.returnERROR;132.133.if(s-len+t-lenlen+t-len-1;ilen+pos;i-136.137.s-datai=s-datai-t-len;138.139.for(i=0;ilen;i+)140.141.s-datai+pos=t-datai;142.143.s-len=s-len+t-len;47.else148.149.if(pos+t-lent-l

8、en+pos-1;i-)152.153.s-datai=s-datai-t-len;154.155.for(i=0;ilen;i+)156.157.s-datai+pos=t-datai;158.159.s-len=MAXNUM;160.161.162.else163.164.for(i=0;idatai+pos=t-datai;167.168.s-len=MAXNUM;169.170.171.-)95

9、.00014.215.returnOK;/删除串intStringDelete(String*s,intpos,intlen)inti;if(pos(s-len-len)returnFALSE;for(i=pos+len-1;ilen;i+)s-datai-len=s-datai;s-len-=len;returnTRUE;简单模式匹配算法()intStringBF(String*s,String*t)inti=0,j=0;while(ilen-1)&jl

10、en-1)if(s-datai=t-dataj)i+;j+;elsei=i-j+1;j=0;if(j(t-len-1)return(i-t-len+1);elsereturnFALSE;/KMP模式匹配算法()/1.计算子串的next()voidGetNext(intnext,String*t)216.inti=1,j=0；217.next0=-1;218.next1=0;219.while(ilen)220.221.if(j=0|t-datai=t-dataj)222.223.+i;224.+j;225.nexti=j;226.227.else228.j=nextj;229.230.231.

11、2.通过next值来计算子串出现的具体位置232.intIndexKmp(String*s,String*t,intpos,intnext)233.234.inti=pos,j=1;235.while(ilen-1&jlen-1)236.237.if(j=0|s-datai=t-dataj)238.239.+i;240.+j;241.242.else243.j=nextj;244.245.if(jt-len-1)246.return(i-t-len+1);247.else248.returnFALSE;249.250./主函数251.intmain()252.253.intnext100;25

12、4.String*s,*t;255.s=(String*)malloc(sizeof(String);256.t=(String*)malloc(sizeof(String);257.intchoice,begin,end,len,a,pos,i;258.while(TRUE)259.260.printf（t请输入操作数：n）；261.262.printf(t1、建立串；n);printf(t2、输出串；n);263.264.printf（t3、求串长度；n）;printf（t4、删除部分字符串；n）;265.266.printf（t5、简单的BF模式匹配算法n）;printf（t6、效率更高

13、的KMP模式匹配算法n）;267.268.269.printf(t7、退出；n);scanf(%d”,&choice);switch(choice)270.271.case1:272.273.StringCreate(s);break;case2:274.275.StringPrint(s);break;case3:276.277.StringLenth(s);break;case4:278.279.printf（请输入删除起始位置：）；scanf（%d”,&begin）;280.281.printf（请输入删除末尾位置：“）；scanf（%d”,&end）;282.283.len=end-b

14、egin+1;StringDelete(s,begin,len);284.285.printf(新串为：)；StringPrint(s);286.287.break;case5:288.289./建立子串StringCreate(t);290.a=StringBF(s,t);291.292.293.printf(匹配位置为：%dn,a);break;case6:294.295.296./建立子串StringCreate(t);GetNext(next,t);297.298.for(i=0;ilen;i+)printf(t%d,nexti);299.300.printf(n);pos=0;301

15、.a=IndexKmp(s,t,pos,next);302.303.printf(匹配位置为：%dn,a);break;case7:return0;TOC o 1-5 h zgetchar();return0;6.测试图psE:vscodec&:加总式杨正宇8dMext总nsicin八rts-v&sdjqkifg/lk,Me-stdaut=Microstrft-MlEi)gine-out-zli5hzlzc.Oyg*1-stderrExe=c：mingw64birigdb,exe1iiiterpreterni1请输入操作数,1、建立串；L输出串；不求串长度;取删除部分字符串；5、简单的B喉式兀

16、配算法入效率更高的KMP模式匹配算法7.退出;1请输入字符用长度:5请痂入第1个字符1请痂入第2个字符2靖输入第士个字符3请输入第4个字符4靖输入第5个字符5请输入操作数;lx建立串；3输出串；3.求串长度；4、删除部分字符串；5、简单的E喉式匹配算法6、效率更高的KMP模式匹配算法7、退出；212545请输入操作数二1.建立串；2、输出串73、求串长度；4删除部分字符串；5”简单的BF模式匹配算法6效率更高的KMP模式匹配算法7、退出；字符串长度为二5请输入操作数；1.建立串；2、输出率；3“求串长度：4、删除部分字符串,5、简单的SF模式匹配算法6效率更高的心1P模式匹配算法7“退出：请输入删除起始位置：2请输入删除末尾位