第5周串第2讲-串的模式匹配

实验三 串的模式匹配

实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 四、程序流程图、算法及运行结果 3-1 #include #include #define MAXSIZE 100 int StrIndex_BF(char s[MAXSIZE],char t[MAXSIZE]) { int i=1,j=1; while (i<=s[0] && j<=t[0] ) { if (s[i]==t[j]){ i++; j++; } else { i=i-j+2; j=1; } } if (j>t[0]) return (i-t[0]); else

return -1; } int main() { char s[MAXSIZE]; char t[MAXSIZE]; int answer, i; printf("S String -->\n "); gets(s); printf("T String -->\n "); gets(t); printf("%d",StrIndex_BF(s,t)); /*验证*/ if((answer=StrIndex_BF(s,t))>=0) { printf("\n"); printf("%s\n", s); for (i = 0; i < answer; i++) printf(" "); printf("%s", t); printf("\n\nPattern Found at location:%d\n", answer); } else printf("\nPattern NOT FOUND.\n"); getch(); return 0; }

模式匹配的KMP算法详解

模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。

字符串的模式匹配算法

在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx”

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

竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——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；否则，匹配失败，算法返回0。 实现代码如下：

/*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=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).

串的模式匹配

《数据结构》课程设计报告 题目：模式匹配算法KMP及其应 用 学院 （系）： 班级： 学生学 号： 姓名： 指导教 师： 日期： 目录

摘要 (1) 一、绪论 (2) 1. 课程设计的背景 (2) 2. 课程设计的意义 (3) 3. 开发平台及其简介 (3) 二、需求分析 (3) 三、可行性分析 (5) 四、概要设计 1. 功能设计要求 (5) 2. 总体结构设计 (6) 3. 抽象数据类型串的定义 (9) 4. 函数调用关系 (10) 5. 主程序调用 (11) 五、详细设计 (12) 1. 宏定义 (12) 2. 数据元素结构定义 (13)

3. 功能具体实现 (13) 4. 主程序和菜单设计 (29) 六、设计和调试分析 (31) 七、测试结果 (33) 八、设计心得体会 (37) 九、用户手册 (37) 一十、附录 (43) 一十一、参考文献 (44) 摘要 本程序主要是通过获取一个子串，或新建一个新的文本文件，或和已有的文本文件进行匹配，分别利用了串的朴素模式匹配算法、串的模式匹配KMP算法、串的模式匹配改进算法等数据结构中学的知识实现了，在和文本文件中的主串进行匹配后返回子串在文本文件中出现的次数和出现位置所在的行的行号。 本程序除了实现串在定长顺序存储结构下的三种模式匹配算法，还实现了串在单链表存储结构下的模式匹配KMP算法，通过比较了串的不同存储结构下串的模式匹配算法，进一步加强了对串的理解及串的各类模式算法的掌握。 在使用串的定长存储结构时，考虑到书本上实现串的KMP算法时，储存串的数组下标是从1开始，为了进一步理解串，本程序另辟蹊径，特地定义了一个结构体，结构体中用来存储串的数组下标是从0开始，实现了串的模式匹配KMP算法。

数据结构第04章 串

第四章串 教学目的与要求 本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。 重点和难点 本章重点是掌握串上实现的模式匹配算法，其也是本章难点。 教学内容 第一节串的基本概念 ４.1.1 基本概念 串：是零个或多个字符组成的有限序列。串中所包含的字符个数称为串的长度。 空串：长度为0的串称为空串，它不包含任何字符。 空白串：仅由一个或多个空格组成的串称为空白串。应注意空串和空白串的区别。 子串、主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身的子串。 子串在主串中的位置：通常，将子串在主串中首次出现时子串首字符对应的主串中的序号定义为子串在主串中的位置。 ２．串的基本运算 （１）求串的长度（Length） （２）串复制 (Copy)： （３）串联接 (Concat)

（４）串比较 (Compare) （５）字符定位(Index) 除上述基本运算外，串运算还有求子串、子串的定位、子串的置换等操作。这些操作，一般可由这些基本操作实现。 第二节串的存储结构 4.2.1串的顺序存储 1.静态存储分配的顺序串 顺序串最简单的描述形式是直接使用定长的字符数组来定义。其定义形式为 # define maxstrsize 256 typedef char Seqstring[maxstrsise]; 利用类型描述符Seqstrsring可定义数组变量存储串，利用特定字符表示串的结束(Ｃ语言用转义字符’\0’) 。例如Seqstrstring s; 变量s可存储长度不超过255个字符的字符串，以’\0’作为串的结束。 顺序串的类型定义也可以象线性表的顺序存储一样，在定义字符数组的基础上，引入描述长度的成员。其定义形式为 # define maxstrsize 256 typedef struct { char ch[maxstrsise]; int length; }Sqestring;

第四章：串

第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, ‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】 A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长 4．已知串S=‘aaab’,其Next数组值为（）。 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’的nextval 为（） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1

字符串匹配算法总结

Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible (业内人士一般简称TAOCP). 稍稍提一下，有个叫H.A.Simon的家伙，不仅拿了Turing Award ，顺手拿了个Nobel Economics Award ，做了AI 的爸爸，还是Chicago Univ的Politics PhD ，可谓全才。 KMP 的思想是这样的： 利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离 比如 模式串ababac这个时候我们发现在c 处不匹配，然后我们看c 前面那串字符串的最大相等前后缀，然后再来移动 下面的两个都是模式串，没有写出来匹配串 原始位置ababa c 移动之后aba bac 因为后缀是已经匹配了的，而前缀和后缀是相等的，所以直接把前缀移动到原来后缀处，再从原来的c 处，也就是现在的第二个b 处进行比较。这就是KMP 。 Horspool算法。 当然，有市场就有竞争，字符串匹配这么大一个市场，不可能让BF 和KMP 全部占了，于是又出现了几个强劲的对手。

串的模式匹配

实验内容与要求 内容： 问题描述：从键盘输入一个目标串S，并输入要匹配的模式串T，利用串的简单的模式匹配和KMP算法，定位模式串在主串中的位置。 要求： 设计要求 首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 主控菜单设计要求：程序运行后，显示一个标题“模式匹配算法”，标题下方给出6个菜单项的内容和输入提示： 1．输入一个主串S 2．输入一个模式串T 3. 计算模式串T的next函数值 4．实现简单模式匹配 5．实现KMP模式匹配 6. 继续/否？（y/n?） #include #include typedef char String[100]; int next[10]; void GetNext(String T,int next[]) { int i=1,j=0; next[1]=0; while(i

j=next[j]; } } void printNext(String T) { int i; for(i=1;i<=T[0];i++) { printf("next[%d]:%d ",i,next[i]); } printf("\n"); } int KMP_INDEX(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0] &&j<=T[0]) { if(j==0||S[i]==T[j]) { i++; j++; } else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0; } int Index(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0] &&j<=T[0]) {

串的朴素模式匹配算法(BF算法)

//算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include #include #define MAXL 255 #define FALSE 0 #define TRUE 1 typedef int Status; typedef unsigned char SString[MAXL+1]; //生成一个其值等于串常量strs的串T void StrAssign(SString &T, char *strs) { int i; T[0] = 0; //0号单元存储字串长度 for(i = 0; strs[i]; i++) //用数组strs给串T赋值 T[i+1] = strs[i]; T[0] = i; } //返回子串T在主串S中第pos个字符开始匹配的位置，若不存在，则返回0 int Index(SString S, SString T, int pos) { int i = pos, j = 1; while(i <= S[0] && j <= T[0]) { if(S[i] == T[j]) //继续比较后面的字符 { i++; j++; } else//指针回退，重新开始匹配 { i = i -j + 2; j = 1; } } if(j > T[0]) return i - T[0]; else return 0;

int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; }

模式匹配KMP算法实验步骤

一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。

改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1aaab ->aaab ->aaab 像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。 到这里，就实现了KMP的大部分内容，然后关键的问题是如何求next值？先看如何用它来进行匹配操作。 将最前面的程序改写成： int Index_KMP(String S,String T,int pos) { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) {

串的模式匹配算法

串的匹配算法——Brute Force (BF)算法 匹配模式的定义 设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。通常把主串S称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串S中找到一个模式串T；不成功则指目标串S中不存在模式串T。 BF算法 Brute-Force算法简称为BF算法，其基本思路是：从目标串S的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串S的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串S中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0. /*T非空。 int index(String S, String T ,int pos) { int i=pos; //用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配int j =1; //j用于子串T中当前位置下标值 while(i<=S[0]&&j<=T[0]) //若i小于S长度且j小于T的长度时循环 { if(S[i]==T[j]) //两个字母相等则继续 { ++i； ++j； } else //指针后退重新开始匹配 { i=i-j+2; //i退回到上次匹配首位的下一位 j=1； } if(j>T[0]) return i-T[0]; else return 0; } }

BF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m 次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m 从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是O(n+m).

C语言字符串模式匹配

数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS);

int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n

串匹配问题：BF算法、KMP算法、BM算法

一、实验内容和目的 1、深刻理解并掌握蛮力算法的设计思想； 2、提高应用蛮力算法设计算法的技能； 3、理解这样一个观点:用蛮力法设计的算法，一般来说，经过适度的努 力后，都可以对算法的第一个版本进行一定程度的改良，改进其时 间性能。 二、实验原理及基本技术路线图（方框原理图） 串匹配问题——给定两个串S=“s1s2…s n” 和T=“t1t2…t m”，在主 串S中查找子串T的过程称为串匹配，也称模式匹配。 串匹配问题属于易解问题。 串匹配问题的特征： （1）算法的一次执行时间不容忽视：问题规模n 很大，常常需要在 大量信息中进行匹配； （2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。 BF算法： 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比 较，若相等，则继续比较两者的后续字符；若不相等，则从主串S 的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配 的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T， 匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。 KMP算法： 1. 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较 完毕 2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到next[j]位置，即j=next[j]；

2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 2.4 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0； BM算法： BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。 设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。

串的模式匹配

实验四顺序串的各种模式匹配 一、实验目的 熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。 二、实验内容 由用户随意输入两个串：主串S和模式串T，设S=‘s1s2…sn’，T=‘t1t2…tm’，且0 #include using namespace std; typedef struct taglin{ int data; taglin* next; }lin; void initlin(lin* &L,int e){ lin* p=L,* s; while(p->next!=NULL) p=p->next; s=(lin*)malloc(sizeof(lin)); s->data=e;

s->next=p->next; p->next=s; } void main(){ int num,e,x,y,count=-1,c=0,e1,t=-2147483648; bool mark=false; lin* L,* tx,* p,* q; L=(lin*)malloc(sizeof(lin)); L->next=NULL; cout<<"输入个数>=2"<>num; if(num<2){ cout<<"输入比2小的值_错误"<>e; initlin(L,e); if(c==0){ e1=e; c++; } if(e>x>>y; if(y>=e) mark=true; if(e1>x) x=e1; tx=L->next; for(;tx->data<=x;tx=tx->next); p=L->next; for(;p!=NULL&&p->next!=tx;p=p->next); q=p; if(!mark){ for(;p!=NULL&&p->data<=y;p=p->next)

第四章 串

第四章串 一、内容提要 1、是数据元素为字符的线性表，串的定义及操作。 2、串的基本操作，编制算法求串的其它操作。 3、串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。静态和动态（块链结构，堆结构）存储的优缺点。 4、朴素模式匹配算法及改进（KMP）算法。 二、学习重点 1、串的基本操作，编写串的其他操作（如index,replace等）。 2、在串的模式匹配中，求匹配串的nextval 函数值。 3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。 5、串操作在存储结构下的实现。 三、例题解析 1、利用串的如下基本运算 create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法 replace(string &s,string t, string v) //本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。

{i=INDEX(s,t);{判s中有无t} IF (i!=0) {CREATE (temp, ‘’);{t为临时串变量，存放部分结果} m=LENGTH(t);n=LENGTH(s); WHILE (i!=0) { ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i-1),v)); //用v替换t形成部分结果 ASSIGN (s,SUBSTR(s, i+m,n-i-m+1)); //t串以后形成新s串 n= n-(i-1)-m; i=INDEX(s,t); } ASSIGN (s,CONCAT(temp,s)); //将剩余s连接临时串t再赋给s } } int index(string s,string t) //本算法求串t在串s中的第一次出现。结果是：若t在s中，则给出串t的第一个字符在串s中的位置，若不存在，则返回0 {j=1;m=length(s); n=length(t); eq=true; WHILE((j<=m-n+1)&& eq ) IF equal(substr(s,j,n),t) eq=false; ELSEj=j+1； IF( j<=m+n-1)return(j); Return(0);

第四章 串 习题及答案

第四章串习题及答案 一、基础知识题 4.1简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 4.2假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么? (4)调用函数strcmp(&s1[5],"ton")的返回值是什么? (5)调用函数stlen(strcat(s1,s2))的返回值是什么? 4.3设T[0..n-1]="adaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T 时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 二、算法设计题： 4.4利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。

4.5利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 4.6以HString为存储表示，写一个求子串的算法。 4.7一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。 4.8写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。 注意： S和P的长度不一定相等。可以使用已有的串操作。 4.9将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。 *4.10利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。 4.11若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 答案： 4.1简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

第四章 串

一、填空题 1. 称为空串；称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 4. 子串的定位运算称为串的模式匹配；称为目标串，称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。 8. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== ; （2）GetHead【GetTail【((a,b),(c,d))】】=== ; （3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ; （4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ; 二、单选题 （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作： Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长 （）3. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF （）4. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。（无第0行第0列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不对 ( ) 5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如? ?a1,1

数据结构 串与模式匹配

常熟理工学院 《数据结构与算法》实验指导与报告书 _2017-2018_____学年第__1__ 学期 专业：物联网工程 实验名称：串与模式匹配 实验地点： N6-210 指导教师：聂盼红 计算机科学与工程学院 2017

实验四串与模式匹配 【实验目的】 1、掌握串的存储表示及基本操作； 2、掌握串的两种模式匹配算法：BF和KMP。 3、了解串的应用。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、串和子串的定义 串：串是由零个或多个任意字符组成的有限序列。 子串：串中任意连续字符组成的子序称为该串的字串。 2、串的模式匹配 串的模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T 称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败 【实1 验内容和要求】/ 1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果： ?求“This is a boy”的串长； ?比较”abc ?3”和“abcde“； 表示空格

?比较”english”和“student“； ?比较”abc”和“abc“； ?截取串”white”，起始2，长度2； ?截取串”white”，起始1，长度7； ?截取串”white”，起始6，长度2； ?连接串”asddffgh”和”12344”；

实验代码： #include #include #define MAXSIZE 100 #define ERROR 0 #define OK 1 /*串的定长顺序存储表示*/ typedef struct { char data[MAXSIZE]; int length; } SqString; int strInit(SqString *s); /*初始化串*/ int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/ int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*/ /*初始化串*/ int strInit(SqString *s) { s->length=0; s->data[0]='\0'; return OK; }/*strInit*/ /*生成一个串*/ int strCreate(SqString *s) { printf("input string :"); gets(s->data); s->length=strlen(s->data); return OK; }/*strCreate*/