欢迎来到天天文库
浏览记录
ID:57313804
大小:18.40 KB
页数:17页
时间:2020-08-11
《串的模式匹配算法实验报告.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一:串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T,子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串,把子串T称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T;不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法,其基本思路是:从目标串s的第一个字符开始和模式串T中的第一个字符比较,若相等,则继续逐个比较后续的字符;否
2、则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推,若从模式串T的第i个字符开始,每个字符依次和目标串s中的对应字符相等,则匹配成功,该算法返回i;否则,匹配失败,算法返回0。 实现代码如下: /*返回子串T在主串s中第pos个字符之后的位置。若不存在,则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标,若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=
3、1; } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度,m为子串长度则 最好的情况是:一配就中,只比较了m次。 最坏的情况是:主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位比较了m次,最后m位也各比较了一次,还要加上m,所以总次数为:(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数,然后取平均,得到一般情况是o(n+m). 篇二:数据结构实验报告-串 实验四串 【实验目的】 1、掌握串的存储表
4、示及基本操作; 2、掌握串的两种模式匹配算法:bF和Kmp。 3、了解串的应用。 【实验学时】 2学时 【实验预习】 回答以下问题: 1、串和子串的定义 串的定义:串是由零个或多个任意字符组成的有限序列。 子串的定义:串中任意连续字符组成的子序列称为该串的子串。 2、串的模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,从主串s的第start个字符开始查找等于子串t的过程称为模式匹配,如果在s中找到等于t的子串,则称匹配成功,函数返回t在s中首次出现的存储位置(或序号);否则,匹配失败,
5、返回0。 【实验内容和要(:串的模式匹配算法实验报告)求】 1、按照要求完成程序exp4_1.c,实现串的相关操作。调试并运行如下测试数据给出运行结果: ?求“Thisisaboy”的串长; ?比较”abc??3”和“abcde“;?表示空格 ?比较”english”和“student“; ?比较”abc”和“abc“; ?截取串”white”,起始2,长度2; ?截取串”white”,起始1,长度7; ?截取串”white”,起始6,长度2; ?连接串”asddffgh”和”12344”; #include
6、#include #definemAxsIZe100 #defineeRRoR0 #defineoK1 /*串的定长顺序存储表示*/ typedefstruct { chardata[mAxsIZe]; intlength; }sqstring; intstrInit(sqstring*s);/*初始化串*/ intstrcreate(sqstring*s);/*生成一个串*/intstrLength(sqstring*s);/*求串的长度*/intstrcompare(sqstring*s1,sqstring*
7、s2);/*两个串的比较*/intsubstring(sqstring*sub,sqstring*s,intpos,intlen);/*求子串*/ intstrconcat(sqstring*t,sqstring*s1,sqstring*s2);/*两个串的连接*/ /*初始化串*/ intstrInit(sqstring*s) { s->length=0; s->data[0]= ; returnoK; }/*strInit*/ /*生成一个串*/ intstrcreate(sqstring*s) { pr
8、intf("inputstring:"); gets(s->data); s->length=strlen(s->data); returnoK; }/*strcreate*/ /*(1)---求串的长度*/
此文档下载收益归作者所有