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

第1页共17页竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告篇一：串的模式匹配算法串的匹配算法——bruteForce(bF)算法匹配模式的定义设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否第2页共17页则，匹配失败，算法返回0。实现代码如下：/*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。intindex(strings,stringT,intpos){inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(ij=1；}if(jT[0])returni-T[0];elsereturn0;}}bF算法的时间复杂度若n为主串长度，m为子串长度则最好的情况是：一配就中，只比较了m次。最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从第3页共17页最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m).篇二：数据结构实验报告-串实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：bF和Kmp。3、了解串的应用。【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。子串的定义：串中任意连续字符组成的子序列称为该串的子串。2、串的模式匹配串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回0。第4页共17页【实验内容和要(:串的模式匹配算法实验报告)求】1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果：?求“Thisisaboy”的串长；?比较”abc??3”和“abcde“；?表示空格?比较”english”和“student“；?比较”abc”和“abc“；?截取串”white”，起始2，长度2；?截取串”white”，起始1，长度7；?截取串”white”，起始6，长度2；?连接串”asddffgh”和”12344”；#include#include#definemAxsIZe100#defineeRRoR0#defineoK1/*串的定长顺序存储表示*/typedefstruct{chardata[mAxsIZe];intlength;}sqstring;第5页共17页intstrInit(sqstring*s);/*初始化串*/intstrcreate(sqstring*s);/*生成一个串*/intstrLength(sqstring*s);/*求串的长度*/intstrcompare(sqstring*s1,sqstring*s2);/*两个串的比较*/intsubstring(sqstring*sub,sqstring*s,intpos,intlen);/*求子串*/intstrconcat(sqstring*t,sqstring*s1,sqstring*s2);/*两个串的连接*//*初始化串*/intstrInit(sqstring*s){s-length=0;s-data[0]=\0;returnoK;}/*strInit*//*生成一个串*/intstrcreate(sqstring*s){printf(inputstring:);gets(s-data);第6页共17页s-length=strlen(s-data);returnoK;}/*strcreate*//*（1）---求串的长度*/intstrLength(sqstring*s){returns-length;}/*strLength*//*（2）---两个串的比较，s1s2返回0，s1intstrcompare(sqstring*s1,sqstring*s2){inti;for(i=0;ilengthi++){if(s1-data[i]s2-data[i]){return1;}if(s1-data[i]data[i]){return-1;}第7页共17页}return0;}/*strcompare*//*（3）---求子串，sub为返回的子串，pos为子串的起始位置，len为子串的长度*/intsubstring(sqstring*sub,sqstring*s,intpos,intlen){inti;if(poss-length||lens-length-pos+1){returneRRoR;}sub-length=0;for(i=0;i{sub-data[i]=s-data[i+pos-1];sub-length++;}sub-data[i]=\0;returnoK;}/*substring*//*（4）---两个串连接，s2连接在s1后，连接后的结第8页共17页果串放在t中*/intstrconcat(sqstring*t,sqstring*s1,sqstring*s2){inti=0,j=0;while(ilength){t-data[i]=s1-data[i];i++;}while(jlength){t-data[i++]=s2-data[j++];}t-data[i]=\0;t-length=s1-length+s2-length;returnoK;}/*strconcat*/intmain(){intn,k,pos,len;sqstrings,t,x;do第9页共17页{printf(\n---string---\n);printf(1.strLentgh\n);printf(2.strcompare\n);printf(3.substring\n);printf(4.strconcat\n);printf(0.exIT\n);printf(\n---string---\n);printf(\ninputchoice:);scanf(%d,getchar();switch(n){case1:printf(\n***showstrLength***\n);strcreate(printf(strLengthis%d\n,strLength(break;case2:printf(\n***showstrcompare***\n);strcreate(strcreate(第10页共17页k=strcompare(/*（5）---调用串比较函数比较s，t*/if(k==0)printf(twostringequal!\n);elseif(kprintf(firststringelseprintf(firststringsecondstring!\n);break;case3:printf(\n***showsubstring***\n);strcreate(printf(inputsubstringpos,len:);scanf(%d,%d,if(substring(elseprintf(posorleneRRoR!\n);break;case4:printf(\n***showsubconcat***\n);strcreate(strcreate(if(strconcat(elseprintf(concateRRoR!\n);第11页共17页break;case0:exit(0);default:break;}}while(n);return0;}2、按照要求完成程序exp4_2.c，实现bFintlength;}sqstring;intstrcreate(sqstring*s);intindexbf(sqstring*s,sqstring*t,intpos);/*串的模式匹配bF*/voidgetnext(sqstring*t,intnext[]);/*Kmp求next值*/篇三：字符串模式匹配算法综述字符串模式匹配算法综述摘要：字符串匹配问题是在给定符号序列（称为文本）中按照一定的匹配条件，搜索给定符号序列或给定符号序列集合中元素（称为模式）出现位置的搜索问题。该问题是计第12页共17页算机科学的基础问题之一，被广泛的应用于各种涉及文字和符号处理的领域中，是网络安全、信息检索、计算生物学等重要领域的关键问题。本文主要介绍了bF算法、Kmp算法、bm算法、bmh算法、Ac算法和Ac-bm算法。关键词：模式匹配，bF算法，Kmp算法，改进算法，bm算法，Ac算法，Ach算法。0.前言字符串是一种线性表,它在计算机应用系统中如文本编辑、情报检索、自然语言翻译有着广泛的应用。在这些应用中常常需要在一堆文字符串中检测是否有某一指定的字符串。设pattern(下文简称p)和Text(下文简称T)是给定的两个字符串,在字符串T中寻找等于p的子串的过程称为模式匹配,其中字符串T称为主串,字符串p称为模式串。如果在字符串T中找到等于p的子串,则称匹配成功,否则匹配失败。比较著名的模式匹配算法有bF算法、Kmp算法、Ac算法和bm算法,本文对所述算法进行探讨。随着计算机技术的快速发展，计算机网络在国民经济中发挥了日益重要的作用，己成为人们日常生活中不可缺少的一部分。同时，网络安全也日益引起人们的关注。1.模式匹配算法1.1单模式匹配算法1.1.1bF（bruceForce）算法第13页共17页1.算法思想从文本字符串T的第一个字符起和模式字符串p中的第一个字符开始比较，若相等，逐个比较后续字符，否则从文本字符串的下一个字符起再重新和模式字符串的第一个字符比较。2.算法描述对于文本字符串T0??????Tk??????Ti??????Tm?k?1??????Tn模式字符串p0??????pj??????pm（1）p和T从左端对齐，使得p0与T0对齐；（2）从左到右匹配p与T的字符，直到出现不匹配的情况，则执行（3），或是p己被完全匹配的情况则结束比较；（3）将p右移一个字符，重新从p的第一个字符开始匹配；（4）重复上述（2）过程，直到p被完全匹配，或p移到T的右端。1.1.2Kmp（Knuthmorrispratt）算法Kmp算法是Knuth等人在bF算法的基础上提出来的。从本质上讲，Kmp算法就是出现不匹配情况下带有智能指针初始化的bF算法。为了在不匹配时重新定位指针，Kmp算法需要进行预处理算出一个next数组来。1.基本思想第14页共17页Kmp算法利用己匹配成功部分的信息，即前缀（模式字符串中存在的相同子串），可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯。2.算法描述当模式匹配执行到比较字符Ti和pj，其中l=i=n，l=j=m。（l）若Ti=pj则继续往右做匹配检测，即对Ti?1和pj?1进行匹配检测。（2）若Ti?pj当j=l，则对Ti?1和pj进行匹配检测，即把模式和正文向右移动一位再从模式的第一个字符进行匹配；若l0j?1??next?j??max?k|0?k?j且p0???pk?1?pj?k?1???pj?1?集合非空?1其