数据结构与算法：Python语言描述字符串

1、数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/1/3 3，字符串，字符串v 字符串的相关概念字符串的相关概念v Python 字符串（回顾）字符串（回顾）v 字符串匹配和算法字符串匹配和算法v 进一步的模式匹配问题进一步的模式匹配问题v 正则表达式正则表达式v Python 的正则表达式的正则表达式v 应用举例应用举例数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/2/字符串字符串n讨论字符串，首先要有一个确定的讨论字符串，首先要有一个确定的字符集字符集q“字符字符”是一个抽象概念，字符集是有穷的一组字符构成的集合是一个抽象概念，字符集

2、是有穷的一组字符构成的集合q人们经常考虑在计算机里使用的标准字符集，实际上，完全可以拿人们经常考虑在计算机里使用的标准字符集，实际上，完全可以拿任意数据元素的集合作为字符集任意数据元素的集合作为字符集n字符串字符串（简称（简称串串）是特殊的线性表，表中元素取自选定的字符集）是特殊的线性表，表中元素取自选定的字符集其不同于一般表的特点是支持其不同于一般表的特点是支持一组以串为对象的操作一组以串为对象的操作n长度长度：串中字符的个数称为串的：串中字符的个数称为串的长度长度q长度为长度为 0 的串称为的串称为空串空串q在任意一个字符集里，只有唯一的一个空串在任意一个字符集里，只有唯一的一个空串n与一

3、般的表类似：与一般的表类似：q字符串里的字符顺序排列，串里的每个字符有其确定位置字符串里的字符顺序排列，串里的每个字符有其确定位置q我们用我们用 0 开始的自然数表示位置开始的自然数表示位置数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/3/字符串字符串n串相等：串的相等基于字符集里的字符定义串相等：串的相等基于字符集里的字符定义s1 和和 s2 相等，如果其长度相等，而且对应位置的各对字符分别相同相等，如果其长度相等，而且对应位置的各对字符分别相同n假定字符集中的字符有一个全序，串的字典序定义如下：假定字符集中的字符有一个全序，串的字典序定义如下：对于串对于串定义

4、定义 s1 s2，如果存在一个如果存在一个 k 使使 ai = bi (i = 0,1, k-1) 而且而且 ak bk 或者或者 n m 而且对而且对 i = 0,1, n-1 都有都有 ai = bi显然，字典序是字符串集合上的一个全序显然，字典序是字符串集合上的一个全序11021101 ,mnbbbsaaasn串与串的最重要运算是拼接（串与串的最重要运算是拼接（concatenate）上面上面 s1 和和 s2 的拼接是串的拼接是串 显然，显然，s 的长度等于的长度等于 s1 和和 s2 的长度之和的长度之和在在 Python 里拼接运算用里拼接运算用 + 表示表示110110mnbbb

5、aaas数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/4/字符串字符串n两个串之间还有一个重要的关系是两个串之间还有一个重要的关系是“子串关系子串关系”n称称 s1 为为 s2 的一个的一个子串子串，如果存在两个串，如果存在两个串 s 和和 s 使下式成立使下式成立s2 = s + s1 + s （借用借用 Python 的写法）的写法）q子串也是串。直观看，子串是原串中连续的一段字符序列形成的串。子串也是串。直观看，子串是原串中连续的一段字符序列形成的串。显然，一个串可以是或者不是另一个串的子串显然，一个串可以是或者不是另一个串的子串q如果如果 s1 是是 s2

6、 的子串，也说的子串，也说 s1 在在 s2 里里出现出现，称，称 s2 里与里与 s1 相同的相同的字符段的第一个字符的位置为字符段的第一个字符的位置为 s1 在在 s2 里里出现的位置出现的位置qs2 里可能出现多个与里可能出现多个与 s1 相同的段，这时说相同的段，这时说 s1 在在 s2 里多次出现里多次出现n注意：注意：s1 在在 s2 中的多个出现可能不独立，相互重叠。例如中的多个出现可能不独立，相互重叠。例如babb 在在 babbabbbbabb 里有三个出现，前两个有重叠里有三个出现，前两个有重叠n根据定义，很显然，空串是任何字符串的子串；另一方面，任何字符串根据定义，很显然

7、，空串是任何字符串的子串；另一方面，任何字符串 s 也都是该串本身的子串也都是该串本身的子串数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/5/字符串字符串n两种特殊子串：两种特殊子串：q如果存在如果存在 s 使使 s2 = s1 + s，称称 s1 为为 s2 的一个的一个前缀前缀q如果存在如果存在 s 使得使得 s2 = s + s1，称称 s1 为为 s2 的一个的一个后缀后缀直观说，一个串的前缀就是该串开头的一段字符构成的子串，后缀就直观说，一个串的前缀就是该串开头的一段字符构成的子串，后缀就是该串最后的一段字符构成的子串是该串最后的一段字符构成的子串显然，

8、空串和显然，空串和 s 既是既是 s 的前缀，也是的前缀，也是 s 的后缀的后缀n其他有用的串运算：其他有用的串运算：q串串 s 的的 n 次幂次幂 sn 是连续是连续 n 个个 s 拼接而成的串（在拼接而成的串（在 Python 语言里语言里用用 s * n 表示）表示）q串替换，指将一个串里的一些（互不重叠的）子串代换为另一些串串替换，指将一个串里的一些（互不重叠的）子串代换为另一些串得到的结果（由于可能重叠，需规定代换的顺序，如从左到右）得到的结果（由于可能重叠，需规定代换的顺序，如从左到右）q还有许多有用的串运算，可以参考还有许多有用的串运算，可以参考 Python 的的 str 类型

9、，或其他语类型，或其他语言的字符串类型（经典是言的字符串类型（经典是 SNOBOL 语言）语言）数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/6/字符串的理论字符串的理论n字符串集合和拼接操作构成了一种代数结构字符串集合和拼接操作构成了一种代数结构q空串是拼接操作的空串是拼接操作的“单位元单位元” （幺元）（幺元） 有结合律，无交换律有结合律，无交换律q串集合加上拼接操作，构成一个半群串集合加上拼接操作，构成一个半群一种典型的非交换半群一种典型的非交换半群q有单位元，因此是一个幺半群有单位元，因此是一个幺半群n关于串的理论有许多研究工作关于串的理论有许多研究工作q

10、基于串和串替换，研究者提出了基于串和串替换，研究者提出了 post 系统系统这是一种与图灵机等价的计算模型这是一种与图灵机等价的计算模型q（串）重写系统（串）重写系统（rewriting system）是计算机理论的一个研究领是计算机理论的一个研究领域，一直非常活跃，有许多重要结果和应用域，一直非常活跃，有许多重要结果和应用数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/7/字符串抽象数据类型字符串抽象数据类型可以考虑下面的字符串抽象数据类型：可以考虑下面的字符串抽象数据类型：ADT String:String(self, sseq) # 基于字符序列基于字符序列s

11、seq建立一个字符串建立一个字符串is_empty(self) # 判断本字符串是否空串判断本字符串是否空串len(self) # 取得字符串的长度取得字符串的长度char(self, index) # 取得字符串中位置取得字符串中位置index的字符的字符substr(self, a, b) # 取得字符串中取得字符串中 a:b 的子串，左闭右开区间的子串，左闭右开区间match(self, string) # 查找串查找串string在本字符串中第一个出现的位置在本字符串中第一个出现的位置concat(self, string) # 做出本字符串与另一字符串做出本字符串与另一字符串stri

12、ng的拼接串的拼接串subst(self, str1, str2) # 做出将本字符串里的子串做出将本字符串里的子串str1 # 都替换为都替换为str2的结果串的结果串最后两个操作可以实现为变动操作或非变动操作（生成满足需要的新串）最后两个操作可以实现为变动操作或非变动操作（生成满足需要的新串）这里的大部分操作都很简单，只有这里的大部分操作都很简单，只有match和和subst操作比较复杂。易见，操作比较复杂。易见，subst 的基础也是的基础也是 match，因为要找，因为要找 str1 在串里的出现在串里的出现子串检索（子串匹配）是字符串的核心操作，后面将详细研究子串检索（子串匹配）是字

13、符串的核心操作，后面将详细研究数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/8/字符串的实现字符串的实现n串是字符的线性序列：串是字符的线性序列：q可采用线性表的实现方式，用顺序表示和链接表示。例如用能动态可采用线性表的实现方式，用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式（如果需要表示可变的字符串）变化大小的顺序表作为实现方式（如果需要表示可变的字符串）q还可以根据串本身的特点和串操作的特点，考虑其他表示方式。当还可以根据串本身的特点和串操作的特点，考虑其他表示方式。当然，无论如何还是基于然，无论如何还是基于顺序存储顺序存储或或/和和链接链接q

14、关键问题：表示方式应能很好支持串的管理和相关操作的实现关键问题：表示方式应能很好支持串的管理和相关操作的实现n字符串表示的两个问题：字符串表示的两个问题：q串内容存储。两个极端：串内容存储。两个极端：1，连续存储在一块存储区；，连续存储在一块存储区；2，一个字符，一个字符存入一个独立存储块，链接起来。也可以采用某种中间方式，把串存入一个独立存储块，链接起来。也可以采用某种中间方式，把串中字符分段保存在一组存储块里，链接起这些存储块中字符分段保存在一组存储块里，链接起这些存储块q串结束的表示，不同字符串长度可能不同，必须表示串到哪里结束。串结束的表示，不同字符串长度可能不同，必须表示串到哪里结束

15、。两种基本方式：两种基本方式：1，用专门数据域记录字符串长度；，用专门数据域记录字符串长度；2，用一个特殊，用一个特殊符号表示串结束（例如符号表示串结束（例如 C 语言的字符串采用这种方式）语言的字符串采用这种方式）数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/9/字符串的实现字符串的实现n现在考虑字符串的操作现在考虑字符串的操作许多串操作是线性表操作的具体实例，包括串拼接许多串操作是线性表操作的具体实例，包括串拼接下面考虑一个特殊的操作下面考虑一个特殊的操作n串替换串替换q牵涉到三个串：被处理的主串牵涉到三个串：被处理的主串 s，作为被替换对象需要从作为被替换对

16、象需要从 s 中替换中替换掉的子串掉的子串 t，以及用于代换以及用于代换 t 的的 tq由于由于 t 可能在可能在 s 中出现多次，因此需要通过一系列具体的子串代换中出现多次，因此需要通过一系列具体的子串代换完成整个替换完成整个替换q由于多次出现可能重叠（回忆前面的例子），只能规定一种代换顺由于多次出现可能重叠（回忆前面的例子），只能规定一种代换顺序（例如从左到右），一次代换破坏的子串不应再代入新串序（例如从左到右），一次代换破坏的子串不应再代入新串q一次子串代换后，应该从代入的新串之后继续工作。即使代入新串一次子串代换后，应该从代入的新串之后继续工作。即使代入新串之后形成的部分能与之后形成的

17、部分能与 t 匹配，也不应在本次替换中考虑匹配，也不应在本次替换中考虑q很容易看到：串替换的关键是找到匹配很容易看到：串替换的关键是找到匹配数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/10/实际语言里的字符串实际语言里的字符串n许多语言提供了标准的字符串功能，如许多语言提供了标准的字符串功能，如qC语言标准库有一组字符串函数（语言标准库有一组字符串函数（string.h），），一些一些C语言系统提供语言系统提供的扩展的字符串库；的扩展的字符串库；C+ 语言标准库里的字符串库语言标准库里的字符串库 qJava 标准库的字符串库标准库的字符串库q许多脚本语言（包括许

18、多脚本语言（包括 Python）提供了功能丰富的字符串库提供了功能丰富的字符串库n许多实际字符串库用动态顺序表结构作为字符串的表示方式许多实际字符串库用动态顺序表结构作为字符串的表示方式q这样既能支持任意长的字符串这样既能支持任意长的字符串q又能比较有效地实现各种重要的字符串操作又能比较有效地实现各种重要的字符串操作n实际上，支持不同的字符串操作，可能需要不同的实现，例如实际上，支持不同的字符串操作，可能需要不同的实现，例如q有些计算工作需要记录和处理极长的字符串，如支持操作有些计算工作需要记录和处理极长的字符串，如支持操作 MB（大大约为约为 106）或更长的字符串，采用连续存储可能带来管理

19、问题）或更长的字符串，采用连续存储可能带来管理问题q被编辑文本也是字符串，实现编辑器操作要考虑专门的字符串表示被编辑文本也是字符串，实现编辑器操作要考虑专门的字符串表示数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/11/Python 字符串字符串nPython 内部类型内部类型 str 是抽象字符串概念的一个实现是抽象字符串概念的一个实现qstr 是不变类型，是不变类型，str 对象创建后的内容（和长度）不变对象创建后的内容（和长度）不变q但不同的但不同的 str 对象长度不同，需要记录对象长度不同，需要记录nPython 采用一体式的连续形式表示采用一体式的连续

20、形式表示 str 对象，见下图对象，见下图其他其他长度长度len串内容存储区串内容存储区.nstr 对象的操作分为两类：对象的操作分为两类：q获取获取 str 对象的信息，如得到串长，检查串内容是否全为数字等对象的信息，如得到串长，检查串内容是否全为数字等q基于基于 str 对象构造新的对象构造新的 str 对象，包括切片，构造小写对象，包括切片，构造小写/大写拷贝，大写拷贝，各种格式化等。切分是构造包含多个字符串的表各种格式化等。切分是构造包含多个字符串的表n一些操作属子串匹配，如一些操作属子串匹配，如 count 检查子串出现次数，检查子串出现次数，endwith 检查后检查后缀，缀，fi

21、nd/index 找子串位置等。这类操作最重要，后面专门讨论找子串位置等。这类操作最重要，后面专门讨论数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/12/字符串操作的实现字符串操作的实现n检查字符串内容的操作可以分为两类检查字符串内容的操作可以分为两类qO(1) 时间的简单操作，包括时间的简单操作，包括 len 和定位访问（也构造新字符串）和定位访问（也构造新字符串）q其他都需要扫描整个串的内容，包括不变序列的共有操作（其他都需要扫描整个串的内容，包括不变序列的共有操作（in、not in、min/max），各种字符类型判断（如是否全为数字），各种字符类型判断（如

22、是否全为数字）o 需通过一个循环逐个检查串中字符完成工作，需通过一个循环逐个检查串中字符完成工作，O(n) 操作操作o 子串查找和匹配的问题后面讨论子串查找和匹配的问题后面讨论n需要构造新字符串的操作情况比较复杂，基本模式都包括两部分工作需要构造新字符串的操作情况比较复杂，基本模式都包括两部分工作1, 为新构造的串安排一块存储为新构造的串安排一块存储2, 根据被操作串（和可能的参数串）构造出一个新串根据被操作串（和可能的参数串）构造出一个新串n以以 sa:b:k 为例，算法：为例，算法：1, 根据根据 a、b、k 算出新字符串的长度算出新字符串的长度2, for i in range(a, b

23、, k) : 拷贝拷贝 si 到新串里的下一个空位到新串里的下一个空位数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/13/字符串匹配（子串查找）字符串匹配（子串查找）n最重要的字符串操作是子串匹配，称为最重要的字符串操作是子串匹配，称为字符串匹配字符串匹配（string matching）或或字符串查找字符串查找（string searching） 【有教科书称为模式匹配有教科书称为模式匹配（pattern match），），但实际上但实际上模式匹配模式匹配是内涵更广的概念是内涵更广的概念】wiki：/wiki/Stri

24、ng_searching_algorithmn字符串匹配问题：字符串匹配问题：假设有两个串（假设有两个串（ti, pj 是字符）是字符） t = t0t1t2 tn-1 称为称为目标串目标串 p = p0p1p2 pm-1 称为称为模式串模式串通常有通常有 m n。字符串匹配就是在字符串匹配就是在 t 中查找与等于中查找与等于 p 的子串的过程的子串的过程（这一定义可以推广，后面讨论）（这一定义可以推广，后面讨论）n如前所述，串匹配是最重要的字符串操作，也是其他许多重要字符串操如前所述，串匹配是最重要的字符串操作，也是其他许多重要字符串操作的基础。实际中作的基础。实际中 n 可能非常大，可能非

25、常大，m 也可以有一定规模，也可能需要也可以有一定规模，也可能需要做许多模式串和做许多模式串和/或许多目标串的匹配，有关算法的效率非常重要或许多目标串的匹配，有关算法的效率非常重要数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/14/串匹配串匹配n许多计算机应用的最基本操作是字符串匹配。如许多计算机应用的最基本操作是字符串匹配。如q用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字或词语），在程序里找拼写错误的标识符等或词语），在程序里找拼写错误的标识符等qemail 程序的垃圾邮件过滤器，程序的垃圾

26、邮件过滤器，google 等网络检索系统等网络检索系统q各种防病毒软件，主要靠在文件里检索病毒模式串各种防病毒软件，主要靠在文件里检索病毒模式串n在分子生物学领域：在分子生物学领域：DNA 细胞核里的一类长分子，在遗传中起着核心细胞核里的一类长分子，在遗传中起着核心作用。作用。DNA 内有四种碱基：腺嘌吟内有四种碱基：腺嘌吟(adenine)，胞嘧啶胞嘧啶(cytosine)，鸟鸟嘌吟嘌吟(guanine)，胸腺嘧啶胸腺嘧啶(thymine)。它们的不同组合形成氨基酸、蛋它们的不同组合形成氨基酸、蛋白质和其他更高级的生命结构白质和其他更高级的生命结构qDNA 片段可看作是片段可看作是a,c,g

27、,t构成的模式，如构成的模式，如 acgatactagacagtq考查在蛋白质中是否出现某个考查在蛋白质中是否出现某个 DNA 片段，可看成与该片段，可看成与该 DNA 片段片段的串匹配问题。的串匹配问题。DNA 分子可以切断和拼接，切断动作由各种酶完分子可以切断和拼接，切断动作由各种酶完成，酶也是采用特定的模式确定剪切位置成，酶也是采用特定的模式确定剪切位置数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/15/串匹配串匹配n实际中模式匹配的规模（实际中模式匹配的规模（n 和和 m）可能非常大，而且有时间要求可能非常大，而且有时间要求q被检索的文本可能很大被检索的文

28、本可能很大q网络搜索需要处理亿万的网页网络搜索需要处理亿万的网页q防病毒软件要在合理时间内检查数以十万计的文件（以防病毒软件要在合理时间内检查数以十万计的文件（以 GB 计）计）q运行在服务器上的邮件过滤程序，可能需要在一秒钟的时间内扫描运行在服务器上的邮件过滤程序，可能需要在一秒钟的时间内扫描数以万计的邮件和附件数以万计的邮件和附件q为疾病为疾病/药物研究药物研究/新作物培养等生物学工程应用，需要用大量新作物培养等生物学工程应用，需要用大量 DNA模式与大量模式与大量 DNA 样本（都是样本（都是 DNA 序列）匹配序列）匹配n由于在计算机科学、生物信息学等许多领域的重要应用，串模式匹配问由

29、于在计算机科学、生物信息学等许多领域的重要应用，串模式匹配问题已成为一个极端重要的计算问题。高效的串匹配算法非常重要题已成为一个极端重要的计算问题。高效的串匹配算法非常重要q有几个集中关注字符串匹配问题的国际学术会议，曾经有过专门的有几个集中关注字符串匹配问题的国际学术会议，曾经有过专门的国际竞赛（见国际竞赛（见 wiki 页和万维网）页和万维网）q目前全世界一大半的计算能力是在做串模式匹配（做目前全世界一大半的计算能力是在做串模式匹配（做 DNA 分析）分析）数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/16/串匹配和算法串匹配和算法n还需注意不同的实际需要，如

30、还需注意不同的实际需要，如q用一个模式在很长的目标串里反复匹配（确定出现位置）用一个模式在很长的目标串里反复匹配（确定出现位置）q一组（可能很多）模式，在一个或一组目标串里确定是否有匹配一组（可能很多）模式，在一个或一组目标串里确定是否有匹配n不同算法在处理不同实际情况时可能有不同的表现不同算法在处理不同实际情况时可能有不同的表现人们已经开发出一批有意义的（有趣）算法（进一步情况见人们已经开发出一批有意义的（有趣）算法（进一步情况见 wiki）n粗看，字符串匹配是一个很简单的问题粗看，字符串匹配是一个很简单的问题q字符串是简单数据（字符）的简单序列，结构也最简单（顺序）字符串是简单数据（字符）

31、的简单序列，结构也最简单（顺序）q很容易想到最简单而直接的算法很容易想到最简单而直接的算法q但事实是：直接而简单的算法并不是高效的算法但事实是：直接而简单的算法并不是高效的算法因为它可能没有很好利用问题的内在结构因为它可能没有很好利用问题的内在结构q字符串匹配貌似简单，但人们已开发出许多字符串匹配貌似简单，但人们已开发出许多“大相径庭的大相径庭的”算法算法数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/17/串匹配的朴素算法串匹配的朴素算法n串匹配的基础是逐个比较字符串匹配的基础是逐个比较字符q如果从目标串的某个位置开始，模式串的每个字符都与目标串里的如果从目标串的

32、某个位置开始，模式串的每个字符都与目标串里的对应字符相同，这就是一个匹配对应字符相同，这就是一个匹配q如果出现一对不同字符，就是不匹配如果出现一对不同字符，就是不匹配n算法设计的关键：算法设计的关键：1，怎样比较字符；，怎样比较字符；2，发现不匹配后下一步怎么做，发现不匹配后下一步怎么做q对上述两点采用不同的策略，就形成了不同的算法对上述两点采用不同的策略，就形成了不同的算法q从下面两个例子可以看到一些情况，更多实例见从下面两个例子可以看到一些情况，更多实例见 wikin朴素匹配算法：朴素匹配算法：1，从左到右匹配；，从左到右匹配；2，发现不匹配时，考虑目标串里的，发现不匹配时，考虑目标串里的

33、下一位置是否存在匹配下一位置是否存在匹配 t a b b b a a p a b a a b a a b a a b a 数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/18/串匹配的朴素算法串匹配的朴素算法n朴素的串匹配算法的一个实现：朴素的串匹配算法的一个实现：def naive_nmatching(t, p): m, n = len(p), len(t) i, j = 0, 0 while i m and j n: # i=m说明找到了匹配说明找到了匹配 if pi = tj: # 字符相同字符相同! 考虑下一对字符考虑下一对字符 i, j = i + 1,

34、j + 1 else: # 字符不同字符不同! 考虑考虑t中下一位置中下一位置 i, j = 0, j - i + 1 if i = m: # 找到匹配找到匹配, 返回其开始下标返回其开始下标 return j - i return -1 # 无匹配无匹配, 返回特殊值返回特殊值n朴素匹配算法简单，易理解，但效率低朴素匹配算法简单，易理解，但效率低造成效率的主要操作是执行中可能出现的回溯：遇字符不等时将模式造成效率的主要操作是执行中可能出现的回溯：遇字符不等时将模式串串 p 右移一个字符，再次从右移一个字符，再次从 p0（重置重置 j = 0 后）开始比较后）开始比较数据结构和算法（Pytho

35、n 语言版）：字符串裘宗燕，2021-9-20-/19/串匹配的朴素算法串匹配的朴素算法n最坏情况是每趟比较都在最后出现不等，最多比较最坏情况是每趟比较都在最后出现不等，最多比较 nm1 趟，总比趟，总比较次数为较次数为 m*(nm1)，所以算法时间复杂性为所以算法时间复杂性为 O(m*n)n最坏情况的一个实例最坏情况的一个实例目标串：目标串：00000000000000000000000000000000000000001模式串：模式串：00000001n朴素算法效率低的原因：把每次字符比较看作完全独立的操作朴素算法效率低的原因：把每次字符比较看作完全独立的操作q完全没有利用字符串本身的特点

36、（每个字符串都是特殊的）完全没有利用字符串本身的特点（每个字符串都是特殊的）q没有利用前面已做过的字符比较得到的信息没有利用前面已做过的字符比较得到的信息n从数学上看，这样做相当于认为目标串和模式串里的字符都是随机量，从数学上看，这样做相当于认为目标串和模式串里的字符都是随机量，而且有无穷多可能取值，两次字符比较相互无关也不可借鉴而且有无穷多可能取值，两次字符比较相互无关也不可借鉴q实际字符串取值来自一个有穷集合实际字符串取值来自一个有穷集合q每个串都有穷。特别是模式串通常不太长，而且可能反复使用每个串都有穷。特别是模式串通常不太长，而且可能反复使用数据结构和算法（Python 语言版）：字符

37、串裘宗燕，2021-9-20-/20/无回溯匹配：无回溯匹配：KMP算法算法nKMP 算法是一个高效串匹配算法。由算法是一个高效串匹配算法。由 D. E. Knuth 和和 V. R. Pratt 提出，提出，J. H. Morris 几乎同时发现，因此称几乎同时发现，因此称 KMP 算法。这是本课程中第一个算法。这是本课程中第一个非平凡算法，基于对问题的深入分析，算法不易理解但效率高非平凡算法，基于对问题的深入分析，算法不易理解但效率高n要理解要理解 KMP 算法，首先需要了解朴素算法的缺陷。现在仔细考察朴素算法，首先需要了解朴素算法的缺陷。现在仔细考察朴素算法的执行过程。设目标串算法的执行

38、过程。设目标串 t: ababcabcacbab，模式串模式串 p: abcac第一趟匹配第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a ba b c a c第四趟匹配第四趟匹配a b a b c a b c a c b a ba b c a c第五趟匹配第五趟匹配a b a b c a b c a c b a ba b c a c第六趟匹配第六趟匹配a b a b c a b c a c b a ba b c

39、 a c模式串为匹配前模式串为匹配前已知，在匹配中已知，在匹配中反复使用反复使用若先对模式串做若先对模式串做细致分析，记录细致分析，记录有用信息（有用信息（ 静态静态预处理），有可预处理），有可能加快匹配能加快匹配数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/21/无回溯匹配：无回溯匹配：KMP算法算法nKMP 算法的基本想法：在匹配失败时，利用已做匹配得到的信息，把算法的基本想法：在匹配失败时，利用已做匹配得到的信息，把模式串尽可能前移。匹配中只做不得不做的字符比较，不回溯模式串尽可能前移。匹配中只做不得不做的字符比较，不回溯n处理同一个实例：处理同一个实例：第

40、一趟匹配第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配第三趟匹配a b a b c a b c a c b a b(a)b c a cn这里的匹配绝不回溯，如果匹配到这里的匹配绝不回溯，如果匹配到 tj 失败（设遇到失败（设遇到 pi tj），），就去找到就去找到某个某个 pki，0 ki i，下一步用下一步用 pki 去与去与 tj 比较比较n要正确前移，对模式要正确前移，对模式 p 的每个的每个 pi，都应能找到相应的都应能找到相应的 pki。问题是，无问题是，

41、无论对怎样的论对怎样的 tj 失败，对相应的失败，对相应的 i，对应对应 ki 都一样吗？都一样吗？数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/22/无回溯匹配：分析无回溯匹配：分析n关键认识：在关键认识：在 pi 匹配失败时，所有匹配失败时，所有 pk（0 k i）都已匹配成功（否则都已匹配成功（否则不会考虑不会考虑 pi 的匹配）。也就是说：的匹配）。也就是说：tj 之前的之前的 i-1 个字符就是个字符就是 p 的前的前 i-1 个字符个字符！：！：原本应该根据原本应该根据 t 的情况确定前移方式，但实际上可以根据的情况确定前移方式，但实际上可以根据 p

42、本身本身的情况确定，可以通过对模式串本身的分析在匹配之前做好的情况确定，可以通过对模式串本身的分析在匹配之前做好n结论：对结论：对 p 中的每个中的每个 i，有一个唯一确定的有一个唯一确定的 ki，与被匹配的串无关。通与被匹配的串无关。通过对模式串过对模式串 p 的预分析，可以得到每个的预分析，可以得到每个 i 对应的对应的 ki 值（值（ ）n设设 p 的长度为的长度为 m，需要对每个需要对每个 i (0 i m) 算出一个算出一个 ki 值并保存，以值并保存，以便在匹配中使用。考虑把这便在匹配中使用。考虑把这 m 个值（个值（i 和和ki 的对应关系）存入一个表的对应关系）存入一个表 pn

43、ext，用用 pnexti 表示与表示与 i 对应的对应的 ki 值值n特殊情况：在特殊情况：在 pi 匹配失败时，有可能发现用匹配失败时，有可能发现用 pi 之前的所有之前的所有 p 字符与字符与 t 字符的比较都没有利用价值，下一步应该从头开始，用字符的比较都没有利用价值，下一步应该从头开始，用 p0 与与 tj+1 比较。比较。遇到这种特殊情况就在遇到这种特殊情况就在 pnexti 里记录里记录 1显然，对任何模式都有：显然，对任何模式都有：pnext 0 = -1数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/23/KMP算法算法n假设已经根据模式串假设已经

44、根据模式串 p 做出了做出了 pnext 表，考虑表，考虑 KMP 算法的实现算法的实现n匹配循环很容易写出，如下：匹配循环很容易写出，如下：while j n and i m: # i=m means a matching if i = -1 : # 遇到遇到 1，比较下一对字符，比较下一对字符 j, i = j+1, i+1 elif tj = pi: # 字符相等，比较下一对字符字符相等，比较下一对字符 j, i = j+1, i+1 else: # 从从 pnext 取得取得 p 下一字符的位置下一字符的位置 i = pnextinif 的前两个分支可以合并：的前两个分支可以合并：wh

45、ile j n and i m: # i=m means a matching if i = -1 or tj = pi: # 比较下一对字符比较下一对字符 j, i = j+1, i+1 else: # 从从 pnext 取得取得 p 下一字符的位置下一字符的位置 i = pnexti数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/24/KMP算法算法n匹配函数的定义：匹配函数的定义：def matching_KMP(t, p, pnext): j, i = 0, 0 n, m = len(t), len(p) while j n and i m: # i=m说明

46、找到了匹配说明找到了匹配 if i = -1 or tj = pi: # 考虑考虑p中下一字符中下一字符 j, i = j+1, i+1 else: # 失败失败! 考虑考虑pnext决定的下一字符决定的下一字符 i = pnexti if i = m: # 找到匹配找到匹配, 返回其下标返回其下标 return j-i return -1 # 无匹配无匹配, 返回特殊值返回特殊值n算法复杂性的关键是循环。注意循环中算法复杂性的关键是循环。注意循环中 j 的值递增，但加一的总次数不的值递增，但加一的总次数不多于多于 n = len(t)。而且。而且 j 递增时递增时 i 值也递增。另一方面值也

47、递增。另一方面 i = pnexti 总使总使 i 值减小，但条件保证其值不小于值减小，但条件保证其值不小于 1，因此，因此 i = pnexti 的执行次数不的执行次数不会多于会多于 i 值递增的次数。循环次数是值递增的次数。循环次数是 O(n)，算法复杂性也是算法复杂性也是 O(n)数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/25/q新位置的前缀子串应该与匹配失败字符之前同长度的子串相同新位置的前缀子串应该与匹配失败字符之前同长度的子串相同q如果在模式串匹配失败时，前面一段里满足上述条件的位置不止一如果在模式串匹配失败时，前面一段里满足上述条件的位置不止一处

48、，只能移到最近的那个位置（保证不遗漏可能的匹配）处，只能移到最近的那个位置（保证不遗漏可能的匹配）KMP算法：生成算法：生成 pnext 表表第二趟匹配第二趟匹配a b a b c a b c a c b a ba b c a c(a)b c a cn现在考虑现在考虑 pnext 表的构造，以下面情况为例表的构造，以下面情况为例已知已知 ki 值只依赖于值只依赖于 p 本身的前本身的前i个字符个字符 t0tj-i-1tj-itj-1 tj p0pi-1pi t0tj-i-1p0pi-1 tj设匹配到设匹配到 pi/tj 时失败时失败t 中位置中位置 j 之前的之前的 i 个字符就个字符就是是

49、p 的前的前 i 个字符个字符数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/26/KMP算法：生成算法：生成 pnext 表表n正确正确 k 值由值由 p 前前 i 个字符形成的子串个字符形成的子串里里相等的前缀和后缀相等的前缀和后缀决定决定取这种前后缀中最长的（前移最短），就能保证不忽略可能的匹配取这种前后缀中最长的（前移最短），就能保证不忽略可能的匹配n如果如果 p0pi-1 最长相等前后缀（不包括最长相等前后缀（不包括 p0pi-1 本身但可为空）的长度本身但可为空）的长度为为 k (0 k i-1)。当当 pi tj 时时 p 应右移应右移 i - k 位

50、，随后比较位，随后比较 pk 与与 tj也就是说，应该把也就是说，应该把 pnexti 设置为设置为 kn求求 pnext 的问题变成对每个的问题变成对每个 i 求求 p 的（前缀）子串的（前缀）子串 p0pi-1 的最长相等的最长相等前后缀的长度。前后缀的长度。KMP 提出了一种巧妙的递推算法提出了一种巧妙的递推算法n正确正确 k 值的情况看下面图示值的情况看下面图示 前缀前缀 后缀后缀t0tj-i-1 p0pk-1pi-kpi-1 tj p0 pk-1pk 前缀前缀模式串的正确前移位置移位，必须模式串的正确前移位置移位，必须保证其前缀保证其前缀 p0 pk-1与与 t 中对应那中对应那些字

51、符匹配，而这实际上也就是与些字符匹配，而这实际上也就是与 pi-k pi-1 匹配匹配数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/27/KMP算法：生成算法：生成 pnext 表表n利用已知利用已知 pnext0= -1 直至直至 pnexti 求求 pnexti+1 的算法：的算法：q假设假设 next i = k。若若pk = pi，则则 p0 pi-kpi 的最大相同前后缀的的最大相同前后缀的长度就是长度就是 k+1，记入记入 pnexti+1，将将 i 值加一后继续递推（循环）值加一后继续递推（循环）q若若pk pi 设设 k 为为 pnextk 的值（

52、设的值（设 k 为为 pnextk，也就是去考虑也就是去考虑前一个更短的保证匹配的前缀，从那里继续检查）前一个更短的保证匹配的前缀，从那里继续检查）1.若若 k 值为值为 -1（一定来自（一定来自 pnext），得到，得到 p0 pi-kpi 中最大相同前中最大相同前后缀的长度为后缀的长度为 0，设设 pnext i+1 = 0，将将 i 值加一后继续递推值加一后继续递推n针对针对 i 递推计算最长相等前后缀的长度递推计算最长相等前后缀的长度。设对设对 i-1 已经算出，于是已经算出，于是p0 pk-1 pi-k pi-1 pi pi+1 p0 pk-1pk pk+1 ？q如果如果 pi =

53、pk，pnexti 应该为应该为 k，继续继续q否则把否则把 p0.pk-1的最长相同前缀移过来继续检查的最长相同前缀移过来继续检查数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/28/KMP算法：生成算法：生成 pnext 表表n生成生成 pnext 表的表的 Python 函数定义函数定义def gen_pnext(p): i, k, m = 0, -1, len(p) pnext = -1 * m # 初始数组元素全为初始数组元素全为 -1 while i m-1: # 生成下一个生成下一个pnext元素值元素值 if k = -1 or pi = pk: i

54、, k = i+1, k+1 pnexti = k # 设置设置pnext元素元素 else: k = pnextk # 退到更短相同前缀退到更短相同前缀 return pnextn求模式串求模式串 p 在目标串在目标串 t 里的匹配，可以写：里的匹配，可以写：i = matching_KMP(t, p, gen_pnext(p)n上述上述 pnext 的生成算法还可以改进，下面讨论的生成算法还可以改进，下面讨论数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/29/生成生成 pnext 表：改进表：改进n设置设置 pnexti 时有一点情况可以考虑：时有一点情况可以

55、考虑：t0tj-i-1p0pj-1tj p0pi-1pi在在 pi tj 时（假设时（假设 pnexti = k），），如果发现如果发现 pi = pk，那么一定那么一定 pk tj 。所以模式串应所以模式串应右右移到移到 pnextk，下一步用，下一步用 pnextk 与与 tj 比较比较n改造的算法只有循环体最后的语句不同：改造的算法只有循环体最后的语句不同：def gen_pnext(p): i, k, m = 0, -1, len(p) pnext = -1 * m while i m-1: # 生成下一个生成下一个pnext元素元素 if k = -1 or pi = pk: i,

56、k = i+1, k+1 if pi = pk : pnexti = pnextk else: pnexti = k else: k = pnextk return pnext数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/30/生成生成 pnext 表：复杂性表：复杂性n算法复杂性的主要因素是循环算法复杂性的主要因素是循环与与 KMP 主算法的分析类似：主算法的分析类似：qi 值递增，但不超过值递增，但不超过 p 的长度的长度 m，说明大循环体执行说明大循环体执行 m 次次qi 加一时加一时 k 也加一，说明也加一，说明 k 值加一值加一 m 次次q内层循环执行总

57、导致内层循环执行总导致 k 值减小，但不会小于值减小，但不会小于 1上面情况说明循环体的执行次数为上面情况说明循环体的执行次数为 O(m)，算法复杂性也是算法复杂性也是 O(m)nKMP 算法包括算法包括 pnext 表构造和实际匹配，表构造和实际匹配，O(m+n)。通常情况通常情况 m re.findall(py.B, python, py2, py342, py1py2py4)pyt, py3, py1, py2数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/56/匹配对象（匹配对象（match 对象）对象）n许多匹配函数在匹配成功时返回一个许多匹配函数在匹配成

58、功时返回一个 match 对象，对象里记录了所完对象，对象里记录了所完成匹配的有关信息，可以取出使用。下面介绍这方面的情况成匹配的有关信息，可以取出使用。下面介绍这方面的情况n首先，这样的匹配结果可以用于逻辑判断，成功时得到的首先，这样的匹配结果可以用于逻辑判断，成功时得到的 match 对象对象总表示逻辑真，不成功得到的总表示逻辑真，不成功得到的 None 表示假。例如表示假。例如match1 = re.search( pt, text)if match1: . match1 . text . # 使用使用 match 对象的处理操作对象的处理操作nmatch 对象提供了一组方法，用于检查与

59、匹配有关的信息。下面介绍对象提供了一组方法，用于检查与匹配有关的信息。下面介绍一些基本用法，更多信息（包括可选参数）见一些基本用法，更多信息（包括可选参数）见 re 包文档包文档在下面介绍中，在下面介绍中，mat 表示通过匹配得到的一个表示通过匹配得到的一个 match 对象对象n取得被匹配的子串：取得被匹配的子串：mat.group()在一次成功匹配中，所用的正则表达式匹配了目标串的一个子串，操在一次成功匹配中，所用的正则表达式匹配了目标串的一个子串，操作作 mat.group() 给出这个子串给出这个子串数据结构和算法（Python 语言版）：字符串裘宗燕，2021-9-20-/57/匹配

60、对象（匹配对象（match 对象）对象）n在目标串里的匹配位置：在目标串里的匹配位置：mat.start()得到得到 mat 代表的成功匹配在目标串里的实际匹配位置，这是目标串的代表的成功匹配在目标串里的实际匹配位置，这是目标串的一个字符位置（下标）一个字符位置（下标）n目标串里被匹配子串的结束位置：目标串里被匹配子串的结束位置：mat.end()这个位置采用常规表示方式。设这个位置采用常规表示方式。设 text 是目标串，有如下关系：是目标串，有如下关系：mat.group() = textmat.start():mat.end()n目标串里被匹配的区间：目标串里被匹配的区间：mat.spa