《实验四模式匹配》由会员分享,可在线阅读,更多相关《实验四模式匹配(2页珍藏版)》请在金锄头文库上搜索。
1、实验四 模式匹配一、实验目的和要求掌握字符串存储结构的描述,学会字符串的模式匹配算法的应用。二、实验内容和原理C语言结构化程序设计思想,结构体及指针和字符数组的应用。三、主要仪器设备装有Visual C+/Turbo C+等C程序编译软件的计算机。四、实验中程序的源码1. 朴素模式匹配算法程序代码如下:#include #include# define maxsize 100typedef struct char strmaxsize; int length ; seqstring;int index(seqstring p, seqstring t) int i,j, succ; i=0;
2、succ=0; while(i=t.length-p.length) & (!succ) j=0 ; succ=1; while (j=p.length-1) & succ) if (p.strj=t.stri+j ) j+; else succ=0; +i; if (succ) return (i-1); else return (-1);void main()seqstring t, p; int pos; scanf(%s,t.str); t.length=strlen(t.str); scanf(%s,p.str); p.length=strlen(p.str); pos=index(
3、p,t); printf(n); if (pos=-1) printf(no found); else printf(the position is %d,pos+1);这里写出程序源代码,见书76页算法4.102. 快速模式匹配算法程序代码如下:# define maxsize 100typedef struct char strmaxsize; int length ; seqstring;void getnext(seqstring p,int next)int i,j; next0=-1; i=0;j=-1; while(ip.length) if(j=-1|p.stri=p.strj) +i;+j;nexti=j; else j=nextj; for(i=0;ip.length;i+) printf(%d,nexti);void main()seqstring p; int next50; scanf(%s,p.str); p.length=strlen(p.str); getnext(p,next);这里写出程序源代码,见书78页算法4.11和79页算法4.12五、实验结果与分析1. 这里写出第一个程序的结果与分析,见书75页基本思想2. 这里写出第二个程序的结果与分析,见书78页基本思想