[数学]4_串.pptVIP

第四章 串 本章目录 4.1 串的定义 串的数据对象 串的相关概念 串的比较 ： 串的抽象数据类型定义 4.2 串的存储结构 串的顺序存储结构 串的链式存储结构 结点大小为1的链式存储结构 串的索引存储结构 串的堆存储 4.3 顺序串的实现 常用C++字符串函数 串类AString的定义 串操作举例 串连接 通过多态实现两个串对象连接 串比较 求子串 串插入 串删除 4.4 模式匹配 模式匹配 BF(Brute-Force)算法基本思想 BF算法示意图 BF算法操作步骤 BF算法示例 BF算法分析：最好情况 BF算法分析：最坏情况 NEXT [j] 计算公式 模式匹配的KMP算法思想 KMP算法操作步骤 KMP示例 KMP算法分析 小结 习题 1、设字符串S=‘aabaabaabaac，P=‘aabaac (1) 给出S和P的next值； (2) 若S作主串，P作模式串，试给出KMP算法的匹配过程。 BF算法 KMP算法 设S和T是两个给定的串，在串S中找等于T的子串的过程称为模式匹配(pattern matching)。其中，S称为主串，T称为模式(pattern)。如果找到，称为匹配成功，否则称为匹配失败。 基本思想 ：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较。重复上述过程，若T中的字符全部比较完毕，则说明匹配成功，返回主串S在本趟比较中的起始位置；否则匹配失败，返回0。 单击右键，选择“播放” Step 1：初始化： 设置两个工作指针i、j，分别指向主串S比较起始位 置和子串T的首字符位置 Step 2：只要主串和子串没有比完，重复下列操作： 2.1 如果s[i]= =t[j]，两指针均后移，即： ++i ； ++j； 否则 2.2 如果没有到主串尾，指针回溯，i回到比较起始位置 的后一个，j回到子串首字符位置，即： i=i-j+1； j=0； Step 3：如果子串比完，则匹配成功，返回子串在主串中的位 置，否则，匹配不成功，返回-1 。 单击右键，选择“播放” 设串S长度为n，串T长度为m。 不成功的匹配都发生在串T的第一个字符。 例如：S=aaaaaaaaaabcdccccc T=bcd 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则： ) ( 2 ) ( ) 1 ( 1 1 m n O m n m i p m n i i + = + = ? + - ′ + - = 不成功的匹配都发生在串T的最后一个字符。 例如：S=aaaaaaaaaaabccccc T=aaab 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此 设串S长度为n，串T长度为m。 模式匹配——KMP算法 为什么BF算法时间性能低？ 在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。 如何在匹配不成功时主串不回溯？ 主串不回溯，模式就需要向右滑动一段距离。 如何确定模式的滑动距离？ i=3，j=3失败； s2=t2;t1≠t2 ∴t1≠s2 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c a c b a b 第 2 趟 a b c a c i=3，j=3失败； s2=t2;t1≠t2 ∴t1≠s2 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c a c b a b a b c a c 第 3 趟 a b a b c a b c a c b a b a b c a c 第 3 趟 i j i=7，j=5失败s4=t2;t1≠t2 ∴t1≠s4 a b a b c a b c a c b a b a