串的模式匹配算法实验报告.docx

《串的模式匹配算法实验报告.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）---求串的长度*/