第七章 字符串 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步