湘潭大学：《计算机算法设计与分析》课程教学资源（PPT课件讲稿）第七章 符号串

第七章 字符串 2021/2/21 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 1 第七章 字符串

字符串的概念 ■字符串是由零个或多个字符组成的有限 序列集合,通常我们把字符串简称为串 在高级语言中一般都是用引号(“)或 单引号(’)括起来,例如,串a1a2an, 我们一般记为“a2an2或‘a1a2an3 2021/221 计算机算法设计与分析 2

2021/2/21 计算机算法设计与分析 2 字符串的概念 ◼ 字符串是由零个或多个字符组成的有限 序列集合，通常我们把字符串简称为串。 ◼ 在高级语言中一般都是用引号（“）或 单引号（’）括起来，例如，串a1 a2…an,， 我们一般记为“a1 a2…an, ”或‘a1 a2…an, ’

串的几个概念 1、长度:串s中字符的个数,记为 length(s) 长度为0的串称为空串。 ■2、子串:串中的连续字符序列。而包含子串 的串称为主串。定义空串是任意串的子串 ■3、位置:字符的位置是它在串中的序号;子 串的位置是它的首字符的位置。 4、串相等:两个串相等当且仅当它们完全 致,即长度和对应位置上的字符都相同 2021/221 计算机算法设计与分析 3

2021/2/21 计算机算法设计与分析 3 串的几个概念 ◼ 1、长度：串s中字符的个数，记为length(s) 。 长度为0的串称为空串。 ◼ 2、子串：串中的连续字符序列。而包含子串 的串称为主串。定义空串是任意串的子串。 ◼ 3、位置：字符的位置是它在串中的序号；子 串的位置是它的首字符的位置。 ◼ 4、串相等：两个串相等当且仅当它们完全一 致，即长度和对应位置上的字符都相同

串的匹配 给定长度为n的串T=tt2…tn(T称为正 文),以及另一个串P pn(P称为 模式),査找模式P在正文T中首次出现或 所有出现的位置的过程称为模式匹配。 2021/22 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 4 串的匹配 ◼ 给定长度为n的串T = t1 t2……tn (T称为正 文)，以及另一个串P = p1p2……pm (P称为 模式)，查找模式P在正文T中首次出现或 所有出现的位置的过程称为模式匹配

简单的串模式匹配算法 ■将模式P看成关键字,从正文T的第1个元 素开始, 逐个与T中的P[0]个元素比较 ■如果这个长度为P[O]的子串与模式P相等, 则匹配成功;否则,又从T的第2个元素 开始进行同样的比较 如此继续T[0]-P[0]+1步。 2021/221 计算机算法设计与分析 5

2021/2/21 计算机算法设计与分析 5 简单的串模式匹配算法 ◼ 将模式P看成关键字，从正文T的第1个元 素开始， ◼ 逐个与 T中的P[0]个元素比较； ◼ 如果这个长度为P[0]的子串与模式P相等， 则匹配成功；否则，又从T的第2个元素 开始进行同样的比较。 ◼ 如此继续T[0] – P[0] + 1步

简单的模式匹配算法 a int StrMatch(SString S, SString P)t whl(i plod return 1-P[OJ: return o 2021/22 计算机算法设计与分析 6

2021/2/21 计算机算法设计与分析 6 简单的模式匹配算法 ◼ int StrMatch(SString S, SString P)｛ ◼ i = 1； j = 1； ◼ while(i P[0]) return i – P[0]； ◼ return 0; ◼ ｝

简单的模式匹配算法的评估 ■在回朔深度不大的情况下,模式匹配算 法的时间复杂度为Om+n) ■在最坏情况下的时间复杂度为O(n*m) 2021/221 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 7 简单的模式匹配算法的评估 ◼ 在回朔深度不大的情况下，模式匹配算 法的时间复杂度为O(m+n) ◼ 在最坏情况下的时间复杂度为O(n*m)

KMP算法 ■KMP算法是D. Knuth与VPra6J. Morris同时 发现的,故称为 Knuth morris pratt算法, ■其思想是:每当匹配过程中出现字符不等时, 不是简单地从正文的下一个字符(即+1)开始重 新比较,而是利用已经得到的“部分匹配”的 结果将模式串向右“滑动”尽可能远的一段距 离后,再进行比较。 KMP算法的时间复杂度为O(n+m) 2021/221 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 8 KMP算法 ◼ KMP算法是D. Knuth与V. Pratt和J. Morris同时 发现的，故称为Knuth_Morris_Pratt算法。 ◼ 其思想是：每当匹配过程中出现字符不等时， 不是简单地从正文的下一个字符(即i+1)开始重 新比较，而是利用已经得到的“部分匹配”的 结果将模式串向右“滑动”尽可能远的一段距 离后，再进行比较。 ◼ KMP算法的时间复杂度为O(n+m)

能向右滑动多远? 于是得到这样的结果: Pr..Pk-1pi P k+1··i-1 而由前次的比较应有:s1k+1…s1=p1k+1…,p1=1° p p p1|…P1 m 显然应有:sk1s1=p1,p 2021/221 计算机算法设计与分析 9

2021/2/21 计算机算法设计与分析 9 能向右滑动多远？ p1 … pk … pj … pm s1 …… si …… sn 当si  pj，就将模式向右移动。假设pk和si相比较： s1 …… si …… sn p1 … pk … pj … pm 显然应有：si–k+1…si–1 = p1…pk–1。 s … p1 … 而由前次的比较应有：si–k+1…si–1 = pj–k+1 …pj–1。 于是得到这样的结果： p1…pk–1 = pj–k+1 …pj–1

滑动的距离只取决于模式 ■模式滑动距离只取决于模式本身,与正文无关。 ■设函数next为当模式中第j个字符与正文中相 应字符“失配”时,在模式中需重新和正文中 该字符进行比较的字符的位置 0当j=1时 a next[]= max (k|1<k<j Ep.Pk-1=pik+lPi) 1当不存在相应的k时 2021/221 计算机算法设计与分析 10

2021/2/21 计算机算法设计与分析 10 滑动的距离只取决于模式 ◼ 模式滑动距离只取决于模式本身，与正文无关。 ◼ 设函数next[j]为当模式中第j个字符与正文中相 应字符“失配”时，在模式中需重新和正文中 该字符进行比较的字符的位置。 0 当j=1时 ◼ next[j] = max {k |1<k<j且p1…pk–1= pj–k+1…pj–1} 1 当不存在相应的k时