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

3，字符串字符串的相关概念Python字符串（回顾）字符串匹配和算法进一步的模式匹配问题正则表达式Python的正则表达式应用举例字符串讨论字符串，首先要有一个确定的字符集“字符”是一个抽象概念，字符集是有穷的一组字符构成的集合人们经常考虑在计算机里使用的标准字符集，实际上，完全可以拿任意数据元素的集合作为字符集字符串（简称串）是特殊的线性表，表中元素取自选定的字符集其不同于一般表的特点是支持一组以串为对象的操作长度：串中字符的个数称为串的长度长度为0的串称为空串在任意一个字符集里，只有唯一的一个空串与一般的表类似：字符串里的字符顺序排列，串里的每个字符有其确定位置我们用0开始的自然数表示位置字符串串相等：串的相等基于字符集里的字符定义s1和s2相等，如果其长度相等，而且对应位置的各对字符分别相同假定字符集中的字符有一个全序，串的字典序定义如下：对于串定义s1<s2，如果存在一个k

使ai=bi(i=0,1,…k-1)而且ak<bk

或者n<m

而且对i=0,1,…n-1

都有ai=bi显然，字典序是字符串集合上的一个全序串与串的最重要运算是拼接（concatenate）上面s1

和s2

的拼接是串显然，s

的长度等于s1

和s2

的长度之和在Python里拼接运算用+表示字符串两个串之间还有一个重要的关系是“子串关系”称s1

为s2

的一个子串，如果存在两个串s和s'使下式成立s2=s+s1+s' （借用Python的写法）子串也是串。直观看，子串是原串中连续的一段字符序列形成的串。显然，一个串可以是或者不是另一个串的子串如果s1

是s2

的子串，也说s1

在s2

里出现，称s2

里与s1

相同的字符段的第一个字符的位置为s1

在s2

里出现的位置s2

里可能出现多个与s1

相同的段，这时说s1

在s2

里多次出现注意：s1在s2中的多个出现可能不独立，相互重叠。例如babb在babbabbbbabb里有三个出现，前两个有重叠根据定义，很显然，空串是任何字符串的子串；另一方面，任何字符串s也都是该串本身的子串字符串两种特殊子串：如果存在s'使s2=s1+s'，称s1

为s2

的一个前缀如果存在s使得s2=s+s1，称s1

为s2

的一个后缀直观说，一个串的前缀就是该串开头的一段字符构成的子串，后缀就是该串最后的一段字符构成的子串显然，空串和s既是s的前缀，也是s的后缀其他有用的串运算：串s的n次幂sn

是连续n个s拼接而成的串（在Python语言里用s*n表示）串替换，指将一个串里的一些（互不重叠的）子串代换为另一些串得到的结果（由于可能重叠，需规定代换的顺序，如从左到右）还有许多有用的串运算，可以参考Python的str类型，或其他语言的字符串类型（经典是SNOBOL语言）字符串的理论字符串集合和拼接操作构成了一种代数结构空串是拼接操作的“单位元”（幺元）有结合律，无交换律串集合加上拼接操作，构成一个半群一种典型的非交换半群有单位元，因此是一个幺半群关于串的理论有许多研究工作基于串和串替换，研究者提出了post系统这是一种与图灵机等价的计算模型（串）重写系统（rewritingsystem）是计算机理论的一个研究领域，一直非常活跃，有许多重要结果和应用字符串抽象数据类型可以考虑下面的字符串抽象数据类型：ADTString: String(self,sseq)#基于字符序列sseq建立一个字符串

is_empty(self)#判断本字符串是否空串

len(self)#取得字符串的长度

char(self,index)#取得字符串中位置index的字符

substr(self,a,b)#取得字符串中[a:b]的子串，左闭右开区间

match(self,string)#查找串string在本字符串中第一个出现的位置

concat(self,string)#做出本字符串与另一字符串string的拼接串

subst(self,str1,str2)#做出将本字符串里的子串str1

#都替换为str2的结果串最后两个操作可以实现为变动操作或非变动操作（生成满足需要的新串）这里的大部分操作都很简单，只有match和subst操作比较复杂。易见，subst的基础也是match，因为要找str1在串里的出现子串检索（子串匹配）是字符串的核心操作，后面将详细研究字符串的实现串是字符的线性序列：可采用线性表的实现方式，用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式（如果需要表示可变的字符串）还可以根据串本身的特点和串操作的特点，考虑其他表示方式。当然，无论如何还是基于顺序存储或/和链接关键问题：表示方式应能很好支持串的管理和相关操作的实现字符串表示的两个问题：串内容存储。两个极端：1，连续存储在一块存储区；2，一个字符存入一个独立存储块，链接起来。也可以采用某种中间方式，把串中字符分段保存在一组存储块里，链接起这些存储块串结束的表示，不同字符串长度可能不同，必须表示串到哪里结束。两种基本方式：1，用专门数据域记录字符串长度；2，用一个特殊符号表示串结束（例如C语言的字符串采用这种方式）字符串的实现现在考虑字符串的操作许多串操作是线性表操作的具体实例，包括串拼接下面考虑一个特殊的操作串替换牵涉到三个串：被处理的主串s，作为被替换对象需要从s中替换掉的子串t，以及用于代换t的t'由于t可能在s中出现多次，因此需要通过一系列具体的子串代换完成整个替换由于多次出现可能重叠（回忆前面的例子），只能规定一种代换顺序（例如从左到右），一次代换破坏的子串不应再代入新串一次子串代换后，应该从代入的新串之后继续工作。即使代入新串之后形成的部分能与t匹配，也不应在本次替换中考虑很容易看到：串替换的关键是找到匹配实际语言里的字符串许多语言提供了标准的字符串功能，如C语言标准库有一组字符串函数（string.h），一些C语言系统提供的扩展的字符串库；C++语言标准库里的字符串库<string>Java标准库的字符串库许多脚本语言（包括Python）提供了功能丰富的字符串库许多实际字符串库用动态顺序表结构作为字符串的表示方式这样既能支持任意长的字符串又能比较有效地实现各种重要的字符串操作实际上，支持不同的字符串操作，可能需要不同的实现，例如有些计算工作需要记录和处理极长的字符串，如支持操作MB（大约为106）或更长的字符串，采用连续存储可能带来管理问题被编辑文本也是字符串，实现编辑器操作要考虑专门的字符串表示Python字符串Python内部类型str是抽象字符串概念的一个实现str是不变类型，str对象创建后的内容（和长度）不变但不同的str对象长度不同，需要记录Python采用一体式的连续形式表示str对象，见下图其他长度len串内容存储区...str对象的操作分为两类：获取str对象的信息，如得到串长，检查串内容是否全为数字等基于str对象构造新的str对象，包括切片，构造小写/大写拷贝，各种格式化等。切分是构造包含多个字符串的表一些操作属子串匹配，如count检查子串出现次数，endwith检查后缀，find/index找子串位置等。这类操作最重要，后面专门讨论字符串操作的实现检查字符串内容的操作可以分为两类O(1)时间的简单操作，包括len和定位访问（也构造新字符串）其他都需要扫描整个串的内容，包括不变序列的共有操作（in、notin、min/max），各种字符类型判断（如是否全为数字）需通过一个循环逐个检查串中字符完成工作，O(n)操作子串查找和匹配的问题后面讨论需要构造新字符串的操作情况比较复杂，基本模式都包括两部分工作1,为新构造的串安排一块存储2,根据被操作串（和可能的参数串）构造出一个新串以s[a:b:k]为例，算法：1,根据a、b、k算出新字符串的长度2,foriinrange(a,b,k):拷贝s[i]到新串里的下一个空位字符串匹配（子串查找）最重要的字符串操作是子串匹配，称为字符串匹配（stringmatching）或字符串查找（stringsearching）

【有教科书称为模式匹配（patternmatch），但实际上模式匹配是内涵更广的概念】wiki：/wiki/String_searching_algorithm字符串匹配问题：假设有两个串（ti,pj

是字符）

t=t0t1t2…tn-1

称为目标串

p=p0p1p2…pm-1

称为模式串通常有m<<n。字符串匹配就是在t中查找与等于p的子串的过程（这一定义可以推广，后面讨论）如前所述，串匹配是最重要的字符串操作，也是其他许多重要字符串操作的基础。实际中n可能非常大，m也可以有一定规模，也可能需要做许多模式串和/或许多目标串的匹配，有关算法的效率非常重要串匹配许多计算机应用的最基本操作是字符串匹配。如用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字或词语），在程序里找拼写错误的标识符等email程序的垃圾邮件过滤器，google等网络检索系统各种防病毒软件，主要靠在文件里检索病毒模式串在分子生物学领域：DNA细胞核里的一类长分子，在遗传中起着核心作用。DNA内有四种碱基：腺嘌吟(adenine)，胞嘧啶(cytosine)，鸟嘌吟(guanine)，胸腺嘧啶(thymine)。它们的不同组合形成氨基酸、蛋白质和其他更高级的生命结构DNA片段可看作是a,c,g,t构成的模式，如acgatactagacagt考查在蛋白质中是否出现某个DNA片段，可看成与该DNA片段的串匹配问题。DNA分子可以切断和拼接，切断动作由各种酶完成，酶也是采用特定的模式确定剪切位置串匹配实际中模式匹配的规模（n和m）可能非常大，而且有时间要求被检索的文本可能很大网络搜索需要处理亿万的网页防病毒软件要在合理时间内检查数以十万计的文件（以GB计）运行在服务器上的邮件过滤程序，可能需要在一秒钟的时间内扫描数以万计的邮件和附件为疾病/药物研究/新作物培养等生物学工程应用，需要用大量DNA模式与大量DNA样本（都是DNA序列）匹配由于在计算机科学、生物信息学等许多领域的重要应用，串模式匹配问题已成为一个极端重要的计算问题。高效的串匹配算法非常重要有几个集中关注字符串匹配问题的国际学术会议，曾经有过专门的国际竞赛（见wiki页和万维网）目前全世界一大半的计算能力是在做串模式匹配（做DNA分析）串匹配和算法还需注意不同的实际需要，如用一个模式在很长的目标串里反复匹配（确定出现位置）一组（可能很多）模式，在一个或一组目标串里确定是否有匹配不同算法在处理不同实际情况时可能有不同的表现人们已经开发出一批有意义的（有趣）算法（进一步情况见wiki）粗看，字符串匹配是一个很简单的问题字符串是简单数据（字符）的简单序列，结构也最简单（顺序）很容易想到最简单而直接的算法但事实是：直接而简单的算法并不是高效的算法因为它可能没有很好利用问题的内在结构字符串匹配貌似简单，但人们已开发出许多“大相径庭的”算法串匹配的朴素算法串匹配的基础是逐个比较字符如果从目标串的某个位置开始，模式串的每个字符都与目标串里的对应字符相同，这就是一个匹配如果出现一对不同字符，就是不匹配算法设计的关键：1，怎样比较字符；2，发现不匹配后下一步怎么做对上述两点采用不同的策略，就形成了不同的算法从下面两个例子可以看到一些情况，更多实例见wiki朴素匹配算法：1，从左到右匹配；2，发现不匹配时，考虑目标串里的下一位置是否存在匹配

t

a

b

b

b

a

a

p

a

b

a

a

b

a

a

b

a

a

b

a

串匹配的朴素算法朴素的串匹配算法的一个实现：defnaive_nmatching(t,p):m,n=len(p),len(t)i,j=0,0whilei<mandj<n:#i==m说明找到了匹配

ifp[i]==t[j]:#字符相同!考虑下一对字符

i,j=i+1,j+1else:#字符不同!考虑t中下一位置

i,j=0,j-i+1ifi==m:#找到匹配,返回其开始下标

returnj-ireturn-1#无匹配,返回特殊值朴素匹配算法简单，易理解，但效率低造成效率的主要操作是执行中可能出现的回溯：遇字符不等时将模式串p右移一个字符，再次从p0（重置j=0后）开始比较串匹配的朴素算法最坏情况是每趟比较都在最后出现不等，最多比较n－m＋1趟，总比较次数为m*(n－m＋1)，所以算法时间复杂性为O(m*n)最坏情况的一个实例目标串：00000000000000000000000000000000000000001模式串：00000001朴素算法效率低的原因：把每次字符比较看作完全独立的操作完全没有利用字符串本身的特点（每个字符串都是特殊的）没有利用前面已做过的字符比较得到的信息从数学上看，这样做相当于认为目标串和模式串里的字符都是随机量，而且有无穷多可能取值，两次字符比较相互无关也不可借鉴实际字符串取值来自一个有穷集合每个串都有穷。特别是模式串通常不太长，而且可能反复使用无回溯匹配：KMP算法KMP算法是一个高效串匹配算法。由D.E.Knuth和V.R.Pratt提出，J.H.Morris几乎同时发现，因此称KMP算法。这是本课程中第一个非平凡算法，基于对问题的深入分析，算法不易理解但效率高要理解KMP算法，首先需要了解朴素算法的缺陷。现在仔细考察朴素算法的执行过程。设目标串t:ababcabcacbab，模式串p:abcac第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbababcac第四趟匹配ababcabcacbababcac第五趟匹配ababcabcacbababcac第六趟匹配ababcabcacbababcac模式串为匹配前已知，在匹配中反复使用若先对模式串做细致分析，记录有用信息（静态预处理），有可能加快匹配无回溯匹配：KMP算法KMP算法的基本想法：在匹配失败时，利用已做匹配得到的信息，把模式串尽可能前移。匹配中只做不得不做的字符比较，不回溯处理同一个实例：第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbab(a)bcac这里的匹配绝不回溯，如果匹配到tj

失败（设遇到pi

tj），就去找到某个pki，0ki<i，下一步用pki

去与tj

比较要正确前移，对模式p的每个pi，都应能找到相应的pki。问题是，无论对怎样的tj

失败，对相应的i，对应ki

都一样吗？无回溯匹配：分析关键认识：在pi

匹配失败时，所有pk（0k<i）都已匹配成功（否则不会考虑pi

的匹配）。也就是说：tj

之前的i-1个字符就是p的前i-1个字符！：原本应该根据t的情况确定前移方式，但实际上可以根据p本身的情况确定，可以通过对模式串本身的分析在匹配之前做好结论：对p中的每个i，有一个唯一确定的ki，与被匹配的串无关。通过对模式串p的预分析，可以得到每个i对应的ki

值（）设p的长度为m，需要对每个i(0i<m)算出一个ki

值并保存，以便在匹配中使用。考虑把这m个值（i和ki

的对应关系）存入一个表pnext，用pnext[i]表示与i对应的ki

值特殊情况：在pi

匹配失败时，有可能发现用pi

之前的所有p字符与t字符的比较都没有利用价值，下一步应该从头开始，用p0

与tj+1

比较。遇到这种特殊情况就在pnext[i]里记录–1显然，对任何模式都有：pnext[0]=-1KMP算法假设已经根据模式串p做出了pnext表，考虑KMP算法的实现匹配循环很容易写出，如下：whilej<nandi<m:#i==mmeansamatchingifi==-1:#遇到–1，比较下一对字符j,i=j+1,i+1elift[j]==p[i]:#字符相等，比较下一对字符j,i=j+1,i+1else:#从pnext取得p下一字符的位置i=pnext[i]if的前两个分支可以合并：whilej<nandi<m:#i==mmeansamatchingifi==-1ort[j]==p[i]:#比较下一对字符j,i=j+1,i+1else:#从pnext取得p下一字符的位置i=pnext[i]KMP算法匹配函数的定义：defmatching_KMP(t,p,pnext):j,i=0,0n,m=len(t),len(p)whilej<nandi<m:#i==m说明找到了匹配

ifi==-1ort[j]==p[i]:#考虑p中下一字符

j,i=j+1,i+1else:#失败!考虑pnext决定的下一字符

i=pnext[i]ifi==m:#找到匹配,返回其下标

returnj-ireturn-1#无匹配,返回特殊值算法复杂性的关键是循环。注意循环中j的值递增，但加一的总次数不多于n=len(t)。而且j递增时i值也递增。另一方面i=pnext[i]总使i值减小，但条件保证其值不小于–1，因此i=pnext[i]的执行次数不会多于i值递增的次数。循环次数是O(n)，算法复杂性也是O(n)新位置的前缀子串应该与匹配失败字符之前同长度的子串相同如果在模式串匹配失败时，前面一段里满足上述条件的位置不止一处，只能移到最近的那个位置（保证不遗漏可能的匹配）KMP算法：生成pnext表第二趟匹配ababcabcacbababcac(a)bcac现在考虑pnext表的构造，以下面情况为例已知ki值只依赖于p本身的前i个字符

t0…tj-i-1tj-i…tj-1

tj…p0…pi-1pi…t0…tj-i-1p0…pi-1tj…‖‖设匹配到pi/tj

时失败t中位置j之前的i个字符就是p的前i个字符KMP算法：生成pnext表正确k值由

p前i个字符形成的子串里相等的前缀和后缀决定取这种前后缀中最长的（前移最短），就能保证不忽略可能的匹配如果p0…pi-1

最长相等前后缀（不包括p0…pi-1

本身但可为空）的长度为k(0k<i-1)。当pi

tj

时p应右移i-k位，随后比较pk

与tj也就是说，应该把pnext[i]设置为k求pnext的问题变成对每个i求p的（前缀）子串p0…pi-1

的最长相等前后缀的长度。KMP提出了一种巧妙的递推算法正确k值的情况看下面图示

前缀

后缀t0…tj-i-1p0…pk-1…pi-k…pi-1tj…p0…pk-1pk…

前缀模式串的正确前移位置移位，必须保证其前缀p0…pk-1与t中对应那些字符匹配，而这实际上也就是与pi-k…pi-1匹配KMP算法：生成pnext表利用已知pnext[0]=-1直至pnext[i]求pnext[i+1]的算法：假设next[i]=k。若pk=pi，则p0…pi-k…pi

的最大相同前后缀的长度就是k+1，记入pnext[i+1]，将i值加一后继续递推（循环）若pk

pi

设k为pnext[k]的值（设k为pnext[k]，也就是去考虑前一个更短的保证匹配的前缀，从那里继续检查）若k值为-1（一定来自pnext），得到p0…pi-k…pi

中最大相同前后缀的长度为0，设pnext[i+1]=0，将i值加一后继续递推针对i递推计算最长相等前后缀的长度。设对i-1已经算出，于是p0………pk-1…pi-k………pi-1pipi+1

…p0………pk-1pkpk+1

…‖‖？如果pi=pk，pnext[i]应该为k，继续否则把p0...pk-1的最长相同前缀移过来继续检查KMP算法：生成pnext表生成pnext表的Python函数定义defgen_pnext(p):i,k,m=0,-1,len(p)pnext=[-1]*m#初始数组元素全为-1whilei<m-1:#生成下一个pnext元素值

ifk==-1orp[i]==p[k]:i,k=i+1,k+1pnext[i]=k#设置pnext元素

else:k=pnext[k]#退到更短相同前缀

returnpnext求模式串p在目标串t里的匹配，可以写：i=matching_KMP(t,p,gen_pnext(p))上述pnext的生成算法还可以改进，下面讨论生成pnext表：改进设置pnext[i]时有一点情况可以考虑：t0…tj-i-1p0…pj-1tj…p0…pi-1pi…‖‖在pi

tj时（假设pnext[i]=k），如果发现pi=pk，那么一定pk

tj。所以模式串应右移到

pnext[k]，下一步用

pnext[k]与

tj比较改造的算法只有循环体最后的语句不同：defgen_pnext(p):i,k,m=0,-1,len(p)pnext=[-1]*mwhilei<m-1:#生成下一个pnext元素

ifk==-1orp[i]==p[k]:i,k=i+1,k+1ifp[i]==p[k]:pnext[i]=pnext[k]else:pnext[i]=kelse:k=pnext[k]returnpnext生成pnext表：复杂性算法复杂性的主要因素是循环与KMP主算法的分析类似：i值递增，但不超过p的长度m，说明大循环体执行m次i加一时k也加一，说明k值加一m次内层循环执行总导致k值减小，但不会小于–1上面情况说明循环体的执行次数为O(m)，算法复杂性也是O(m)KMP算法包括pnext表构造和实际匹配，O(m+n)。通常情况m<<n，因此可认为算法复杂性为O(n)。显然优于O(m*n)KMP算法KMP算法的一个重要优点是执行中不回溯。在处理从外部（外存/网络等）获取的文本时这种特性特别有价值，因为可以一边读一边匹配，不回头重读就不需要保存被匹配串KMP算法的优势KMP算法特别适合需要多次使用一个模式串的情况和存在许多匹配的情况（如在大文件里反复找一个单词）相应pnext表只需建立一次。这种情况下可以考虑定义一个模式类型，将pnext表作为模式的一个成分人们还提出了其他的模式匹配算法（参看wiki）另一经典算法由Boyer和Moore提出，采用自右向左的匹配方式。如果字符集较大且匹配很罕见（许多实际情况如此，如在文章里找单词，在邮件里找垃圾过滤关键字），其速度可能远高于KMP算法有兴趣的同学可以自己找相关材料读一读模式匹配问题前面讨论的串匹配基于最简单的字符比较以常规的字符串作为模式比较的一方是模式串，另一方是一个字符串的所有可能子串匹配中考察的是模式串与目标串的所有可能子串之间的相等关系基本串匹配有很广泛的应用，前面举过一些例子，如正文编辑器中最常用的操作是查找和替换网络搜索引擎，基本功能就是在网页中检查检索串的匹配实际使用中，存在着许多不同的场景，如用一个模式串，在目标串里反复检索，找出一些或者所有出现在一个目标串里检查是否出现了一组模式串中的任何一个在一批目标串里检查一个或一组模式串是否出现，等等模式匹配的进一步问题实际中还经常需要（希望）考虑一些更一般的问题，例如一个目录下所有以.py结尾的文件名文件里所有形为href="…"的段（HTML网页里的网页链接）DNA片段里以某碱基段开始以另一碱基段结束的片段计算机可执行文件中的某种片段模式（例如检查病毒），以一种形式的片段开始到另一片段结束，其中出现了某些片段等等这种匹配中考虑的不是一个字符串，而是一集字符串可能有穷，也可能无穷罗列（枚举）的方式不适合这里的需要，因为可能很多或无穷多要处理这种匹配问题，就需要考虑字符串集合的描述问题，以及是否属于一个字符串集合的匹配问题模式匹配的进一步问题有关字符串集合的描述和匹配，需要考虑两个问题：怎样描述被考虑的那个串集合？需要一种严格描述方式，能描述很多（所有？）有用的字符串集合。“系统化的”描述方式就是一种描述串检索模式的语言（简单串匹配的“模式语言”就是字符串本身）如何（或，是否可能）高效实现所希望的检查（匹配）模式描述语言的功能很强，就可能描述更多更复杂的模式（对应的，字符串集合），但匹配算法的复杂性也会提高。这方面有许多理论结果模式语言变得比较复杂以后，或许只能做出具有指数复杂性的匹配算法，这种情况使模式语言变得没有实用意义如果模式语言进一步复杂，模式匹配问题甚至可能变为不可计算问题。也就是说，根本不可能写出完成匹配的算法。这样的描述语言就完全没有实际价值了有意义的模式描述语言是描述能力和处理效率之间的合理平衡模式匹配的进一步问题如果大家对DOS操作系统或者Windows命令窗口（cmd）有些了解，可能会知道描述文件名的“通配符”在Windows系统里搜索文件，也会用到Windows/DOS的文件名描述中可以使用两个通配符*和?写在文件名字符串里的?可以与任何实际字符匹配*可与任意一串字符匹配例：*.py与所有以py为扩展名的文件名匹配在普通字符串的基础上增加通配符，形成了一种功能更强的模式语言一个模式描述一集字符串，例如a?b描述所有3个字符的串，其首字符为a，尾字符为b，中间字符任意能描述无穷字符串集合，例如a*描述了所有以a开头的字符串但，只是加入了通配符的模式语言还不够灵活（描述能力不够强）正则表达式一种很有意义的实用模式语言是正则表达式（RegularExpression,或称regex、regexp、RE、re），由逻辑学家Kleene提出一个具体的正则表达式，描述字符集上的一个字符串集合正则表达式语言的基本成分是字符集里的普通字符，另外还有几种特殊的组合结构（以及表示组合的括号）正则表达式里的普通字符只与该字符本身匹配顺序组合：若

匹配s，

匹配t，那么匹配st选择组合|：若

匹配s，

匹配t，

|匹配s也匹配t星号*：与0段或者任意多段与

匹配的序列的拼接串匹配例：abc只与串abc匹配a(b*)(c*)与所有一个a之后任意个b再后任意个c的串匹配a((b|c)*)与所有一个a后任意个b和c组成的序列匹配正则表达式这里不需要通配符通配符?可以用|描述（由于字符集是有穷集）通配符*可以通过|和星号描述正则表达式在实际的信息处理中非常有用人们以各种形式将其纳入编程语言或者语言的标准库存在很多不同设计，它们都是理论的正则表达式的子集或变形，基于对易用性和实现效率等方面的考虑，还可能有些扩充许多脚本语言提供正则表达式功能，一些常规语言正在或计划把正则表达式纳入标准库，C/C++/Java等语言也有正则表达式包经过在Perl语言里的精炼，基本形成了一套比较标准的形式可以看到许多有关正则表达式的书籍或文章，把正则表达式说成是程序员必备的重要武器，等等。网上的讨论很热闹，有若干书籍正则表达式有关书籍Python正则表达式Python的正则表达式功能由标准包re提供。正则表达式可以帮助我们实现一些复杂的字符串操作。正确使用这个包需要理解正则表达式的描述规则和效用理解使用正则表达式的各种方法正则表达式采用Python字符串的形式描述（引号括起的字符序列）在用于一些特殊的操作时，一个具有正则表达式形式的字符串代表一种字符串模式，它能与特定的一集字符串匹配正则表达式的描述形式实际上构成一种特殊的“小语言”语法：re规定的特殊描述规则语义：一个正则表达式所描述的那一集字符串Python文档HOWTO里有一节RegularExpressionHOWTO。网上有些介绍Python正则表达式的网页，一些Python书籍里有讨论原始字符串在介绍Python正则表达式前，先介绍原始字符串（文字量）的概念原始字符串（rawstring）是Python里一种写字符串文字量的形式，其值（和普通文字量一样）就是str类型的对象原始字符串的形式是在普通字符串文字量前加r或R前缀，如R"abcdefg"r"C:\courses\pathon\progs"原始字符串里的\不作为换意符，在相应str对象里原样保留除了位于单/双引号前的反斜线符号引入原始字符串机制，只是为了使一些字符串的写法简单r"C:\courses\pathon\progs"的等价写法是：

"C:\\courses\\pathon\\progs"写模式匹配正文里的\时情况更麻烦，匹配一个\需要写\\\\有关详情见Python文档的HOWYO。后面将提到两个常用情况正则表达式Python正则表达式包re规定了一组特殊字符，称为“元字符”。它们在匹配字符串时起着特殊的作用。这种字符一共14个.^$*+?\|{}[]()

注意：这些字符在（常规）字符串里都是普通字符（“\”除外），只有在把字符串作为正则表达式使用时，它们有特殊的意义非特殊字符称为常规字符，是描述正则表达式的基础正则表达式串里的常规字符在匹配中只与自己匹配如果一个正则表达式串只包含常规字符，它就只能与自己匹配。也就是说，常规字符串是最基本的正则表达式在介绍正则表达式元字符的使用之前，先介绍re包提供的几个操作可以通过这些操作去使用正则表达式（还有其他方式，后面介绍）在下面函数说明中，参数表里的pattern

表示描述正则表达式的字符串（模式串），string

表示被处理的字符串，repl

表示替换串正则表达式生成正则表达式对象：pile(pattern,flag=0)从pattern生成对应的正则表达式对象。可用于下面几个操作。例：r1=pile("abc")生成"abc"对应的正则表达式对象赋给变量r1re包的操作都有flag选项。re专门提供了一组特殊标记，这里不考虑实际上，下面几个操作都能自动从pattern串生成正则表达式对象。用compile生成对象并记入变量，可以避免在重复使用中重复生成。下面函数的pattern参数都可以用正则表达式串或对象作为实参检索：re.search(pattern,string,flag=0)在string

里检索与pattern

匹配的子串。如找到就返回一个match类型的对象；没找到时返回Nonematch对象里记录成功匹配的相关信息，可以根据需要取出和使用。也可以简单地把它作为一个真值用于逻辑判断正则表达式匹配：re.match(pattern,string,flag=0)检查string是否有与pattern匹配的前缀，匹配成功时返回相应的match对象，否则返回None。例：re.search(r1,"aaabcbcbabcb")成功，但re.match(r1,"aaabcbcbabcb")返回None分割：re.split(pattern,string,maxsplit=0,flags=0)以pattern作为分割串将string分段，maxsplit指明分割数，0表示做完整个string。函数返回分割得到的字符串的表。例

re.split('',"abcabbarenotthesame")

得到：['abc','abb','are','not','the','same']

re.split("","1234")#分割出了几个空串

得到：['1','2','','3','','','4']正则表达式找到所有匹配串：re.findall(pattern,string,flags=0)本函数返回一个表，其元素按顺序给出string里与pattern匹配的（从左到右非重叠的）各个子串如果模式里只有常规字符，做这种匹配的价值不大，因为结果表里所有的字符串相同。但用一般的正则表达式模式，情况就会不同还有操作后面介绍，下面逐步介绍正则表达式的情况。正则表达式的描述如前所说，Python标准库包re的正则表达式就是一类特殊形式的字符串，可用于re里定义的一些函数，完成一些字符串操作正则表达式的最基本组合是顺序组合，若

匹配s，

匹配t，那么匹配s+t（s,t为字符串，Python写法s+t是两个字符串的拼接）注意，在正则表达式里，同样可以（也常常需要）写普通Python字符串使用的换意字符，如\n表示换行，\t表示制表符等正则表达式里的空格也是常规字符，它只与自己匹配下面分门别类介绍一些特殊的描述形式，需要注意两点：一种表达式（或元符号）的构造形式（描述形式）这种表达式能匹配怎样的字符串（集合）字符组字符组表达式[...]匹配括号中列出的任一个字符[abc]

可以匹配字符a或b或c区间形式[0-9]是顺序列出的缩写，匹配所有十进制数字字符[0-9a-zA-Z]

匹配所有字母（英文字母）和数字[^...]中的^表示求补，这种模式匹配所有未在括号里列出的字符[^0-9]匹配所有非十进制数字的字符[^\t\v\n\f\r]

匹配所有非空白字符（非空格/制表符/换行符）如果需要在字符组里包括^，就不能放在第一个位置，或者写\^；如果需要在字符组包括-

]，也必须写\-或\]圆点字符.匹配任意一个字符a..b匹配所有以a开头b结束的四字符串a[1-9][0-9]匹配a10,a11,...,a99常用字符组为了方便，re用换意串形式定义了几个常用字符组，包括：\d：与十进制数字匹配，等价于[0-9]\D：与非十进制数字的所有字符匹配，等价于[^0-9]\s：与所有空白字符匹配，等价于[\t\v\n\f\r]\S：与所有非空白字符匹配，等价于[^\t\v\n\f\r]\w：与所有字母数字字符匹配，等价于[0-9a-zA-Z]\W：与所有非字母数字字符匹配，等价于[^0-9a-zA-Z]还有些类似描述，提供这些只是为了使用方便p\w\w\w与p开头随后三个字母数字字符的串匹配重复常希望写重复匹配的模式（部分），任意次或若干次重复基本重复运算符是*，*与

的0次或任意多次出现匹配re.split('[,]*',s)

将串按空格和逗号（任意个）切分re.split('[,]*','12,34,,5')

得到['1','2','3','4','5']re.split('a*','abbaaabbdbbabbababbabb')

得到['','bb','bbdbb','bb','b','bb','bb']注意，re.match('ab*','abbbbbbc')时，模式可以与a匹配，与ab匹配，等等，它究竟匹配那个串？两种可能贪婪匹配：与有可能匹配的最长子串匹配在这里ab*匹配abbbbbb，*运算符做贪婪匹配非贪婪匹配：与有可能匹配的最短子串匹配重复与*略微不同的重复运算符+表示1次或多次重复例：描述正整数的一种简单模式'\d+'，等价于'\d\d*'可选（片段）用?运算符表示?

表示0次或1次重复例，描述整数（表示整数的字符串）的一种简单模式'-?\d+'确定次数的重复用{n}表示，{n}与

匹配的串的n次重复匹配描述北京常规的固话号码：'(010-)?[2-9][0-9]{7}'注意：这种表达式描述的通常是实际字符串集合的超集，但可以用注意：上面描述中出现了圆括号，描述?的作用范围*,?,{3}

有作用范围问题（优先级），它们作用于最小表达式'010-?'表示其中的'–'可选，'(010-)?'表示整个段可选重复重复范围用{m,n}表示，{m,n}与

匹配的串的m到n次重复匹配a{3,7}与3到7个a构成的串匹配go{2,10}gle与google,gooogle,...,goooooooooogle匹配重复范围中的m和n均可以省略，{,n}表示{0,n}，而{m,}表示{m,infinity}。另外几种重复都可以用这个形式表示：{n}等价于{n,n}，?等价于{0,1}*等价于{0,infinity}，+等价于{1,infinity}*+?{m,n}

都采取贪婪匹配策略，与被匹配串中最长的合适子串匹配（因为它们可能出现更大的模式里，要照顾上下文的需要）与这些运算符对应的有一组非贪婪匹配运算符*?+???{m,n}?（各运算符后增加一个问号）的语义与上面几个运算符分别对应，但采用非贪婪匹配（最小匹配）的策略选择选择运算符|描述两种或多种情况之一的匹配。如果

或者与一个串匹配，那么

|就与之匹配a|b|c

可以匹配a或者b或者c，[abc]

可以看作其简写。后者更简洁方便，有时还能简写如[a-z]，但只能用于单字符选择'0+|[1-9]\d*'

匹配Python程序的十进制整数（注意，Python把负号看作运算符）。如果已知为独立字段，就可以用这个模式。但它会与0123的前段0匹配。进一步考虑还有上下文要求（如需排除abc123,

a123b里的123），这方面的问题后面考虑|的结合力最弱，比顺序组合还弱。上面描述不需要括号实例：匹配国内固定电话号码：'0\d{2}-\d{8}|0\d{3}-\d{7,8}'注意，这个正则表达式描述的是实际集合的超集，如两位区号实际上只有010/020/021/022，这段可写为

0(10|20|21|22|23)-\d{8}，另一段可以精化为0[3-9]\d{2}-\d{7,8}首尾匹配行首匹配：以^符号开头的模式，只能与一行的前缀子串匹配re.search('^for','booksforchildren')得到None行尾匹配：以$符号结尾的模式，只与一行的后缀匹配re.search('fish$','catsliketoeatfishes')得到None注意，“一行的”前缀/后缀包括整个被匹配串的前缀和后缀。如串里有换行符，还包括换行符前的子串（一行的后缀）和其后的子串（前缀）串首匹配：\A开头的模式只与被匹配串的前缀匹配串尾匹配：\Z结束的模式只与被匹配串的后缀匹配至此我们已经介绍了所有14个元字符应特别提出换意字符\，以它作为引导符定义了一批换意元字符，如\d,\D

等。它还用于在模式串里写非打印字符（如\t,\n,...）和\\等，在[]里写\^,\-,\]单词边界两个换意元字符用于描述特殊子串的边界\b描述单词边界，它表示单词边界匹配一个空串。单词是字母数字的连续序列，边界就是非字母数字字符或无字符（串开头/结束）这里有个糟糕的问题：在Python字符串中\b表示退格符，而在re的正则表达式里\b表示单词边界。两种办法：将\双写，它表示把\本身送给pile，如'\\b123\\b'不匹配abc123a等里的123，但匹配(123,123)里的123用Python原始字符串，其中的\不换意。上面的模式可写为r'\b123\b'实例：匹配Python整数的模式可写为'\\b(0+|[1-9]\d*)\\b'用原始字符串可简单地写r'\b(0+|[1-9]\d*)\b'。例如写 re_int=r'\b(0+|[1-9]\d*)\b'单词边界实例：一般的可能带正负号的整数，可以考虑用模式'[+-]?\\b(0+|[1-9]\d*)\\b'但它匹配x+5

里的+5，但不匹配3+-5里的-5。写这种表达式和使用时，都需要考虑被匹配对象的情况例：求一个Python程序里出现的所有整数之和defsumInt(fname):re_int='\\b(0+|[1-9]\d*)\\b'inf=open(fname)ifinf==None:return0ilist=map(int,re.findall(re_int,inf.read()))#可改为分行读入s=0forninilist:s+=nreturns边界\B是\b的补，也是匹配空串，但要求相应位置是字母或数字实例：>>>re.findall('py.\B','python,py2,py342,py1py2py4')['pyt','py3','py1','py2']匹配对象（match对象）许多匹配函数在匹配成功时返回一个match对象，对象里记录了所完成匹配的有关信息，可以取出使用。下面介绍这方面的情况首先，这样的匹配结果可以用于逻辑判断，成功时得到的match对象总表示逻辑真，不成功得到的None表示假。例如match1=re.search(pt,text)ifmatch1:...match1...text...#使用match对象的处理操作match对象提供了一组方法，用于检查与匹配有关的信息。下面介绍一些基本用法，更多信息（包括可选参数）见re包文档在下面介绍中，mat

表示通过匹配得到的一个match对象取得被匹配的子串：mat.group()在一次成功匹配中，所用的正则表达式匹配了目标串的一个子串，操作mat.group()给出这个子串匹配对象（match对象）在目标串里的匹配位置：mat.start()得到mat

代表的成功匹配在目标串里的实际匹配位置，这是目标串的一个字符位置（下标）目标串里被匹配子串的结束位置：mat.end()这个位置采用常规表示方式。设text是目标串，有如下关系：mat.group()==text[mat.start():mat.end()]目标串里被匹配的区间：mat.span()得到匹配的开始和结束位置形成的二元组mat.span()==mat.start(),mat.end()mat.re和mat.string分别取得得到这个match对象所做匹配的正则表达式对象和目标串应用实例见后模式里的组（group）正则表达式描述中的另一个重要概念是组（group）圆括号括起的模式段(...)也是模式，它与被括子模式匹配的串匹配。但在此同时还确定了一个被匹配的“组”（字符段）成功匹配得到的组从0开始编号，可以通过mat.group(n)获取组0就是整个模式匹配的串，用mat.group()获得（默认参数）模式里每对圆括号确定一个组，按开括号的顺序编号，例如m=re.search('.((.)e)f','abcdef')#执行后：m.group()是'cdef'，m.group(1)是'de'，m.group(2)是'd'm.groups()得到包含从编号1开始的各组的序对m.groups()得到('de','d')成功匹配确定的各个组可用\n

形式在模式里其他地方“引用”，表示要求在这个位置匹配同一个子串。这里的n表示一个整数序号模式里的组例：r'(.{2})\1'

可匹配'okok'

或'nono'，不匹配'nooh'注意，组编号应该是\1,\2等，但在普通字符串里，\1表示二进制编码为1（经常可以看到被写成0x01）的那个（特殊）字符，而现在需要模式串里出现\1,\2等为此上面模式需要写成'(.{2})\\1'，或者用原始字符串形式简化写法，写为r'(.{2})\1'(?...)形式的片段称为“扩充表示”，