數(shù)據(jù)結(jié)構(gòu)與算法：Python語(yǔ)言描述 字符串

3，字符串字符串的相關(guān)概念Python字符串（回顧）字符串匹配和算法進(jìn)一步的模式匹配問(wèn)題正則表達(dá)式Python的正則表達(dá)式應(yīng)用舉例字符串討論字符串，首先要有一個(gè)確定的字符集“字符”是一個(gè)抽象概念，字符集是有窮的一組字符構(gòu)成的集合人們經(jīng)?？紤]在計(jì)算機(jī)里使用的標(biāo)準(zhǔn)字符集，實(shí)際上，完全可以拿任意數(shù)據(jù)元素的集合作為字符集字符串（簡(jiǎn)稱串）是特殊的線性表，表中元素取自選定的字符集其不同于一般表的特點(diǎn)是支持一組以串為對(duì)象的操作長(zhǎng)度：串中字符的個(gè)數(shù)稱為串的長(zhǎng)度長(zhǎng)度為0的串稱為空串在任意一個(gè)字符集里，只有唯一的一個(gè)空串與一般的表類似：字符串里的字符順序排列，串里的每個(gè)字符有其確定位置我們用0開(kāi)始的自然數(shù)表示位置字符串串相等：串的相等基于字符集里的字符定義s1和s2相等，如果其長(zhǎng)度相等，而且對(duì)應(yīng)位置的各對(duì)字符分別相同假定字符集中的字符有一個(gè)全序，串的字典序定義如下：對(duì)于串定義s1<s2，如果存在一個(gè)k

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

或者n<m

而且對(duì)i=0,1,…n-1

都有ai=bi顯然，字典序是字符串集合上的一個(gè)全序串與串的最重要運(yùn)算是拼接（concatenate）上面s1

和s2

的拼接是串顯然，s

的長(zhǎng)度等于s1

和s2

的長(zhǎng)度之和在Python里拼接運(yùn)算用+表示字符串兩個(gè)串之間還有一個(gè)重要的關(guān)系是“子串關(guān)系”稱s1

為s2

的一個(gè)子串，如果存在兩個(gè)串s和s'使下式成立s2=s+s1+s' （借用Python的寫(xiě)法）子串也是串。直觀看，子串是原串中連續(xù)的一段字符序列形成的串。顯然，一個(gè)串可以是或者不是另一個(gè)串的子串如果s1

是s2

的子串，也說(shuō)s1

在s2

里出現(xiàn)，稱s2

里與s1

相同的字符段的第一個(gè)字符的位置為s1

在s2

里出現(xiàn)的位置s2

里可能出現(xiàn)多個(gè)與s1

相同的段，這時(shí)說(shuō)s1

在s2

里多次出現(xiàn)注意：s1在s2中的多個(gè)出現(xiàn)可能不獨(dú)立，相互重疊。例如babb在babbabbbbabb里有三個(gè)出現(xiàn)，前兩個(gè)有重疊根據(jù)定義，很顯然，空串是任何字符串的子串；另一方面，任何字符串s也都是該串本身的子串字符串兩種特殊子串：如果存在s'使s2=s1+s'，稱s1

為s2

的一個(gè)前綴如果存在s使得s2=s+s1，稱s1

為s2

的一個(gè)后綴直觀說(shuō)，一個(gè)串的前綴就是該串開(kāi)頭的一段字符構(gòu)成的子串，后綴就是該串最后的一段字符構(gòu)成的子串顯然，空串和s既是s的前綴，也是s的后綴其他有用的串運(yùn)算：串s的n次冪sn

是連續(xù)n個(gè)s拼接而成的串（在Python語(yǔ)言里用s*n表示）串替換，指將一個(gè)串里的一些（互不重疊的）子串代換為另一些串得到的結(jié)果（由于可能重疊，需規(guī)定代換的順序，如從左到右）還有許多有用的串運(yùn)算，可以參考Python的str類型，或其他語(yǔ)言的字符串類型（經(jīng)典是SNOBOL語(yǔ)言）字符串的理論字符串集合和拼接操作構(gòu)成了一種代數(shù)結(jié)構(gòu)空串是拼接操作的“單位元”（幺元）有結(jié)合律，無(wú)交換律串集合加上拼接操作，構(gòu)成一個(gè)半群一種典型的非交換半群有單位元，因此是一個(gè)幺半群關(guān)于串的理論有許多研究工作基于串和串替換，研究者提出了post系統(tǒng)這是一種與圖靈機(jī)等價(jià)的計(jì)算模型（串）重寫(xiě)系統(tǒng)（rewritingsystem）是計(jì)算機(jī)理論的一個(gè)研究領(lǐng)域，一直非常活躍，有許多重要結(jié)果和應(yīng)用字符串抽象數(shù)據(jù)類型可以考慮下面的字符串抽象數(shù)據(jù)類型：ADTString: String(self,sseq)#基于字符序列sseq建立一個(gè)字符串

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

len(self)#取得字符串的長(zhǎng)度

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

substr(self,a,b)#取得字符串中[a:b]的子串，左閉右開(kāi)區(qū)間

match(self,string)#查找串string在本字符串中第一個(gè)出現(xiàn)的位置

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

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

#都替換為str2的結(jié)果串最后兩個(gè)操作可以實(shí)現(xiàn)為變動(dòng)操作或非變動(dòng)操作（生成滿足需要的新串）這里的大部分操作都很簡(jiǎn)單，只有match和subst操作比較復(fù)雜。易見(jiàn)，subst的基礎(chǔ)也是match，因?yàn)橐襰tr1在串里的出現(xiàn)子串檢索（子串匹配）是字符串的核心操作，后面將詳細(xì)研究字符串的實(shí)現(xiàn)串是字符的線性序列：可采用線性表的實(shí)現(xiàn)方式，用順序表示和鏈接表示。例如用能動(dòng)態(tài)變化大小的順序表作為實(shí)現(xiàn)方式（如果需要表示可變的字符串）還可以根據(jù)串本身的特點(diǎn)和串操作的特點(diǎn)，考慮其他表示方式。當(dāng)然，無(wú)論如何還是基于順序存儲(chǔ)或/和鏈接關(guān)鍵問(wèn)題：表示方式應(yīng)能很好支持串的管理和相關(guān)操作的實(shí)現(xiàn)字符串表示的兩個(gè)問(wèn)題：串內(nèi)容存儲(chǔ)。兩個(gè)極端：1，連續(xù)存儲(chǔ)在一塊存儲(chǔ)區(qū)；2，一個(gè)字符存入一個(gè)獨(dú)立存儲(chǔ)塊，鏈接起來(lái)。也可以采用某種中間方式，把串中字符分段保存在一組存儲(chǔ)塊里，鏈接起這些存儲(chǔ)塊串結(jié)束的表示，不同字符串長(zhǎng)度可能不同，必須表示串到哪里結(jié)束。兩種基本方式：1，用專門數(shù)據(jù)域記錄字符串長(zhǎng)度；2，用一個(gè)特殊符號(hào)表示串結(jié)束（例如C語(yǔ)言的字符串采用這種方式）字符串的實(shí)現(xiàn)現(xiàn)在考慮字符串的操作許多串操作是線性表操作的具體實(shí)例，包括串拼接下面考慮一個(gè)特殊的操作串替換牽涉到三個(gè)串：被處理的主串s，作為被替換對(duì)象需要從s中替換掉的子串t，以及用于代換t的t'由于t可能在s中出現(xiàn)多次，因此需要通過(guò)一系列具體的子串代換完成整個(gè)替換由于多次出現(xiàn)可能重疊（回憶前面的例子），只能規(guī)定一種代換順序（例如從左到右），一次代換破壞的子串不應(yīng)再代入新串一次子串代換后，應(yīng)該從代入的新串之后繼續(xù)工作。即使代入新串之后形成的部分能與t匹配，也不應(yīng)在本次替換中考慮很容易看到：串替換的關(guān)鍵是找到匹配實(shí)際語(yǔ)言里的字符串許多語(yǔ)言提供了標(biāo)準(zhǔn)的字符串功能，如C語(yǔ)言標(biāo)準(zhǔn)庫(kù)有一組字符串函數(shù)（string.h），一些C語(yǔ)言系統(tǒng)提供的擴(kuò)展的字符串庫(kù)；C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)里的字符串庫(kù)<string>Java標(biāo)準(zhǔn)庫(kù)的字符串庫(kù)許多腳本語(yǔ)言（包括Python）提供了功能豐富的字符串庫(kù)許多實(shí)際字符串庫(kù)用動(dòng)態(tài)順序表結(jié)構(gòu)作為字符串的表示方式這樣既能支持任意長(zhǎng)的字符串又能比較有效地實(shí)現(xiàn)各種重要的字符串操作實(shí)際上，支持不同的字符串操作，可能需要不同的實(shí)現(xiàn)，例如有些計(jì)算工作需要記錄和處理極長(zhǎng)的字符串，如支持操作MB（大約為106）或更長(zhǎng)的字符串，采用連續(xù)存儲(chǔ)可能帶來(lái)管理問(wèn)題被編輯文本也是字符串，實(shí)現(xiàn)編輯器操作要考慮專門的字符串表示Python字符串Python內(nèi)部類型str是抽象字符串概念的一個(gè)實(shí)現(xiàn)str是不變類型，str對(duì)象創(chuàng)建后的內(nèi)容（和長(zhǎng)度）不變但不同的str對(duì)象長(zhǎng)度不同，需要記錄Python采用一體式的連續(xù)形式表示str對(duì)象，見(jiàn)下圖其他長(zhǎng)度len串內(nèi)容存儲(chǔ)區(qū)...str對(duì)象的操作分為兩類：獲取str對(duì)象的信息，如得到串長(zhǎng)，檢查串內(nèi)容是否全為數(shù)字等基于str對(duì)象構(gòu)造新的str對(duì)象，包括切片，構(gòu)造小寫(xiě)/大寫(xiě)拷貝，各種格式化等。切分是構(gòu)造包含多個(gè)字符串的表一些操作屬子串匹配，如count檢查子串出現(xiàn)次數(shù)，endwith檢查后綴，find/index找子串位置等。這類操作最重要，后面專門討論字符串操作的實(shí)現(xiàn)檢查字符串內(nèi)容的操作可以分為兩類O(1)時(shí)間的簡(jiǎn)單操作，包括len和定位訪問(wèn)（也構(gòu)造新字符串）其他都需要掃描整個(gè)串的內(nèi)容，包括不變序列的共有操作（in、notin、min/max），各種字符類型判斷（如是否全為數(shù)字）需通過(guò)一個(gè)循環(huán)逐個(gè)檢查串中字符完成工作，O(n)操作子串查找和匹配的問(wèn)題后面討論需要構(gòu)造新字符串的操作情況比較復(fù)雜，基本模式都包括兩部分工作1,為新構(gòu)造的串安排一塊存儲(chǔ)2,根據(jù)被操作串（和可能的參數(shù)串）構(gòu)造出一個(gè)新串以s[a:b:k]為例，算法：1,根據(jù)a、b、k算出新字符串的長(zhǎng)度2,foriinrange(a,b,k):拷貝s[i]到新串里的下一個(gè)空位字符串匹配（子串查找）最重要的字符串操作是子串匹配，稱為字符串匹配（stringmatching）或字符串查找（stringsearching）

【有教科書(shū)稱為模式匹配（patternmatch），但實(shí)際上模式匹配是內(nèi)涵更廣的概念】wiki：/wiki/String_searching_algorithm字符串匹配問(wèn)題：假設(shè)有兩個(gè)串（ti,pj

是字符）

t=t0t1t2…tn-1

稱為目標(biāo)串

p=p0p1p2…pm-1

稱為模式串通常有m<<n。字符串匹配就是在t中查找與等于p的子串的過(guò)程（這一定義可以推廣，后面討論）如前所述，串匹配是最重要的字符串操作，也是其他許多重要字符串操作的基礎(chǔ)。實(shí)際中n可能非常大，m也可以有一定規(guī)模，也可能需要做許多模式串和/或許多目標(biāo)串的匹配，有關(guān)算法的效率非常重要串匹配許多計(jì)算機(jī)應(yīng)用的最基本操作是字符串匹配。如用編輯器或字處理系統(tǒng)工作時(shí)，在文本中查找單詞或句子（中文字或詞語(yǔ)），在程序里找拼寫(xiě)錯(cuò)誤的標(biāo)識(shí)符等email程序的垃圾郵件過(guò)濾器，google等網(wǎng)絡(luò)檢索系統(tǒng)各種防病毒軟件，主要靠在文件里檢索病毒模式串在分子生物學(xué)領(lǐng)域：DNA細(xì)胞核里的一類長(zhǎng)分子，在遺傳中起著核心作用。DNA內(nèi)有四種堿基：腺嘌吟(adenine)，胞嘧啶(cytosine)，鳥(niǎo)嘌吟(guanine)，胸腺嘧啶(thymine)。它們的不同組合形成氨基酸、蛋白質(zhì)和其他更高級(jí)的生命結(jié)構(gòu)DNA片段可看作是a,c,g,t構(gòu)成的模式，如acgatactagacagt考查在蛋白質(zhì)中是否出現(xiàn)某個(gè)DNA片段，可看成與該DNA片段的串匹配問(wèn)題。DNA分子可以切斷和拼接，切斷動(dòng)作由各種酶完成，酶也是采用特定的模式確定剪切位置串匹配實(shí)際中模式匹配的規(guī)模（n和m）可能非常大，而且有時(shí)間要求被檢索的文本可能很大網(wǎng)絡(luò)搜索需要處理億萬(wàn)的網(wǎng)頁(yè)防病毒軟件要在合理時(shí)間內(nèi)檢查數(shù)以十萬(wàn)計(jì)的文件（以GB計(jì)）運(yùn)行在服務(wù)器上的郵件過(guò)濾程序，可能需要在一秒鐘的時(shí)間內(nèi)掃描數(shù)以萬(wàn)計(jì)的郵件和附件為疾病/藥物研究/新作物培養(yǎng)等生物學(xué)工程應(yīng)用，需要用大量DNA模式與大量DNA樣本（都是DNA序列）匹配由于在計(jì)算機(jī)科學(xué)、生物信息學(xué)等許多領(lǐng)域的重要應(yīng)用，串模式匹配問(wèn)題已成為一個(gè)極端重要的計(jì)算問(wèn)題。高效的串匹配算法非常重要有幾個(gè)集中關(guān)注字符串匹配問(wèn)題的國(guó)際學(xué)術(shù)會(huì)議，曾經(jīng)有過(guò)專門的國(guó)際競(jìng)賽（見(jiàn)wiki頁(yè)和萬(wàn)維網(wǎng)）目前全世界一大半的計(jì)算能力是在做串模式匹配（做DNA分析）串匹配和算法還需注意不同的實(shí)際需要，如用一個(gè)模式在很長(zhǎng)的目標(biāo)串里反復(fù)匹配（確定出現(xiàn)位置）一組（可能很多）模式，在一個(gè)或一組目標(biāo)串里確定是否有匹配不同算法在處理不同實(shí)際情況時(shí)可能有不同的表現(xiàn)人們已經(jīng)開(kāi)發(fā)出一批有意義的（有趣）算法（進(jìn)一步情況見(jiàn)wiki）粗看，字符串匹配是一個(gè)很簡(jiǎn)單的問(wèn)題字符串是簡(jiǎn)單數(shù)據(jù)（字符）的簡(jiǎn)單序列，結(jié)構(gòu)也最簡(jiǎn)單（順序）很容易想到最簡(jiǎn)單而直接的算法但事實(shí)是：直接而簡(jiǎn)單的算法并不是高效的算法因?yàn)樗赡軟](méi)有很好利用問(wèn)題的內(nèi)在結(jié)構(gòu)字符串匹配貌似簡(jiǎn)單，但人們已開(kāi)發(fā)出許多“大相徑庭的”算法串匹配的樸素算法串匹配的基礎(chǔ)是逐個(gè)比較字符如果從目標(biāo)串的某個(gè)位置開(kāi)始，模式串的每個(gè)字符都與目標(biāo)串里的對(duì)應(yīng)字符相同，這就是一個(gè)匹配如果出現(xiàn)一對(duì)不同字符，就是不匹配算法設(shè)計(jì)的關(guān)鍵：1，怎樣比較字符；2，發(fā)現(xiàn)不匹配后下一步怎么做對(duì)上述兩點(diǎn)采用不同的策略，就形成了不同的算法從下面兩個(gè)例子可以看到一些情況，更多實(shí)例見(jiàn)wiki樸素匹配算法：1，從左到右匹配；2，發(fā)現(xiàn)不匹配時(shí)，考慮目標(biāo)串里的下一位置是否存在匹配

t

a

b

b

b

a

a

p

a

b

a

a

b

a

a

b

a

a

b

a

串匹配的樸素算法樸素的串匹配算法的一個(gè)實(shí)現(xiàn)：defnaive_nmatching(t,p):m,n=len(p),len(t)i,j=0,0whilei<mandj<n:#i==m說(shuō)明找到了匹配

ifp[i]==t[j]:#字符相同!考慮下一對(duì)字符

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

i,j=0,j-i+1ifi==m:#找到匹配,返回其開(kāi)始下標(biāo)

returnj-ireturn-1#無(wú)匹配,返回特殊值樸素匹配算法簡(jiǎn)單，易理解，但效率低造成效率的主要操作是執(zhí)行中可能出現(xiàn)的回溯：遇字符不等時(shí)將模式串p右移一個(gè)字符，再次從p0（重置j=0后）開(kāi)始比較串匹配的樸素算法最壞情況是每趟比較都在最后出現(xiàn)不等，最多比較n－m＋1趟，總比較次數(shù)為m*(n－m＋1)，所以算法時(shí)間復(fù)雜性為O(m*n)最壞情況的一個(gè)實(shí)例目標(biāo)串：00000000000000000000000000000000000000001模式串：00000001樸素算法效率低的原因：把每次字符比較看作完全獨(dú)立的操作完全沒(méi)有利用字符串本身的特點(diǎn)（每個(gè)字符串都是特殊的）沒(méi)有利用前面已做過(guò)的字符比較得到的信息從數(shù)學(xué)上看，這樣做相當(dāng)于認(rèn)為目標(biāo)串和模式串里的字符都是隨機(jī)量，而且有無(wú)窮多可能取值，兩次字符比較相互無(wú)關(guān)也不可借鑒實(shí)際字符串取值來(lái)自一個(gè)有窮集合每個(gè)串都有窮。特別是模式串通常不太長(zhǎng)，而且可能反復(fù)使用無(wú)回溯匹配：KMP算法KMP算法是一個(gè)高效串匹配算法。由D.E.Knuth和V.R.Pratt提出，J.H.Morris幾乎同時(shí)發(fā)現(xiàn)，因此稱KMP算法。這是本課程中第一個(gè)非平凡算法，基于對(duì)問(wèn)題的深入分析，算法不易理解但效率高要理解KMP算法，首先需要了解樸素算法的缺陷?，F(xiàn)在仔細(xì)考察樸素算法的執(zhí)行過(guò)程。設(shè)目標(biāo)串t:ababcabcacbab，模式串p:abcac第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbababcac第四趟匹配ababcabcacbababcac第五趟匹配ababcabcacbababcac第六趟匹配ababcabcacbababcac模式串為匹配前已知，在匹配中反復(fù)使用若先對(duì)模式串做細(xì)致分析，記錄有用信息（靜態(tài)預(yù)處理），有可能加快匹配無(wú)回溯匹配：KMP算法KMP算法的基本想法：在匹配失敗時(shí)，利用已做匹配得到的信息，把模式串盡可能前移。匹配中只做不得不做的字符比較，不回溯處理同一個(gè)實(shí)例：第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbab(a)bcac這里的匹配絕不回溯，如果匹配到tj

失?。ㄔO(shè)遇到pi

tj），就去找到某個(gè)pki，0ki<i，下一步用pki

去與tj

比較要正確前移，對(duì)模式p的每個(gè)pi，都應(yīng)能找到相應(yīng)的pki。問(wèn)題是，無(wú)論對(duì)怎樣的tj

失敗，對(duì)相應(yīng)的i，對(duì)應(yīng)ki

都一樣嗎？無(wú)回溯匹配：分析關(guān)鍵認(rèn)識(shí)：在pi

匹配失敗時(shí)，所有pk（0k<i）都已匹配成功（否則不會(huì)考慮pi

的匹配）。也就是說(shuō)：tj

之前的i-1個(gè)字符就是p的前i-1個(gè)字符?。涸緫?yīng)該根據(jù)t的情況確定前移方式，但實(shí)際上可以根據(jù)p本身的情況確定，可以通過(guò)對(duì)模式串本身的分析在匹配之前做好結(jié)論：對(duì)p中的每個(gè)i，有一個(gè)唯一確定的ki，與被匹配的串無(wú)關(guān)。通過(guò)對(duì)模式串p的預(yù)分析，可以得到每個(gè)i對(duì)應(yīng)的ki

值（）設(shè)p的長(zhǎng)度為m，需要對(duì)每個(gè)i(0i<m)算出一個(gè)ki

值并保存，以便在匹配中使用?？紤]把這m個(gè)值（i和ki

的對(duì)應(yīng)關(guān)系）存入一個(gè)表pnext，用pnext[i]表示與i對(duì)應(yīng)的ki

值特殊情況：在pi

匹配失敗時(shí)，有可能發(fā)現(xiàn)用pi

之前的所有p字符與t字符的比較都沒(méi)有利用價(jià)值，下一步應(yīng)該從頭開(kāi)始，用p0

與tj+1

比較。遇到這種特殊情況就在pnext[i]里記錄–1顯然，對(duì)任何模式都有：pnext[0]=-1KMP算法假設(shè)已經(jīng)根據(jù)模式串p做出了pnext表，考慮KMP算法的實(shí)現(xiàn)匹配循環(huán)很容易寫(xiě)出，如下：whilej<nandi<m:#i==mmeansamatchingifi==-1:#遇到–1，比較下一對(duì)字符j,i=j+1,i+1elift[j]==p[i]:#字符相等，比較下一對(duì)字符j,i=j+1,i+1else:#從pnext取得p下一字符的位置i=pnext[i]if的前兩個(gè)分支可以合并：whilej<nandi<m:#i==mmeansamatchingifi==-1ort[j]==p[i]:#比較下一對(duì)字符j,i=j+1,i+1else:#從pnext取得p下一字符的位置i=pnext[i]KMP算法匹配函數(shù)的定義：defmatching_KMP(t,p,pnext):j,i=0,0n,m=len(t),len(p)whilej<nandi<m:#i==m說(shuō)明找到了匹配

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

j,i=j+1,i+1else:#失敗!考慮pnext決定的下一字符

i=pnext[i]ifi==m:#找到匹配,返回其下標(biāo)

returnj-ireturn-1#無(wú)匹配,返回特殊值算法復(fù)雜性的關(guān)鍵是循環(huán)。注意循環(huán)中j的值遞增，但加一的總次數(shù)不多于n=len(t)。而且j遞增時(shí)i值也遞增。另一方面i=pnext[i]總使i值減小，但條件保證其值不小于–1，因此i=pnext[i]的執(zhí)行次數(shù)不會(huì)多于i值遞增的次數(shù)。循環(huán)次數(shù)是O(n)，算法復(fù)雜性也是O(n)新位置的前綴子串應(yīng)該與匹配失敗字符之前同長(zhǎng)度的子串相同如果在模式串匹配失敗時(shí)，前面一段里滿足上述條件的位置不止一處，只能移到最近的那個(gè)位置（保證不遺漏可能的匹配）KMP算法：生成pnext表第二趟匹配ababcabcacbababcac(a)bcac現(xiàn)在考慮pnext表的構(gòu)造，以下面情況為例已知ki值只依賴于p本身的前i個(gè)字符

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

tj…p0…pi-1pi…t0…tj-i-1p0…pi-1tj…‖‖設(shè)匹配到pi/tj

時(shí)失敗t中位置j之前的i個(gè)字符就是p的前i個(gè)字符KMP算法：生成pnext表正確k值由

p前i個(gè)字符形成的子串里相等的前綴和后綴決定取這種前后綴中最長(zhǎng)的（前移最短），就能保證不忽略可能的匹配如果p0…pi-1

最長(zhǎng)相等前后綴（不包括p0…pi-1

本身但可為空）的長(zhǎng)度為k(0k<i-1)。當(dāng)pi

tj

時(shí)p應(yīng)右移i-k位，隨后比較pk

與tj也就是說(shuō)，應(yīng)該把pnext[i]設(shè)置為k求pnext的問(wèn)題變成對(duì)每個(gè)i求p的（前綴）子串p0…pi-1

的最長(zhǎng)相等前后綴的長(zhǎng)度。KMP提出了一種巧妙的遞推算法正確k值的情況看下面圖示

前綴

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

前綴模式串的正確前移位置移位，必須保證其前綴p0…pk-1與t中對(duì)應(yīng)那些字符匹配，而這實(shí)際上也就是與pi-k…pi-1匹配KMP算法：生成pnext表利用已知pnext[0]=-1直至pnext[i]求pnext[i+1]的算法：假設(shè)next[i]=k。若pk=pi，則p0…pi-k…pi

的最大相同前后綴的長(zhǎng)度就是k+1，記入pnext[i+1]，將i值加一后繼續(xù)遞推（循環(huán)）若pk

pi

設(shè)k為pnext[k]的值（設(shè)k為pnext[k]，也就是去考慮前一個(gè)更短的保證匹配的前綴，從那里繼續(xù)檢查）若k值為-1（一定來(lái)自pnext），得到p0…pi-k…pi

中最大相同前后綴的長(zhǎng)度為0，設(shè)pnext[i+1]=0，將i值加一后繼續(xù)遞推針對(duì)i遞推計(jì)算最長(zhǎng)相等前后綴的長(zhǎng)度。設(shè)對(duì)i-1已經(jīng)算出，于是p0………pk-1…pi-k………pi-1pipi+1

…p0………pk-1pkpk+1

…‖‖？如果pi=pk，pnext[i]應(yīng)該為k，繼續(xù)否則把p0...pk-1的最長(zhǎng)相同前綴移過(guò)來(lái)繼續(xù)檢查KMP算法：生成pnext表生成pnext表的Python函數(shù)定義defgen_pnext(p):i,k,m=0,-1,len(p)pnext=[-1]*m#初始數(shù)組元素全為-1whilei<m-1:#生成下一個(gè)pnext元素值

ifk==-1orp[i]==p[k]:i,k=i+1,k+1pnext[i]=k#設(shè)置pnext元素

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

returnpnext求模式串p在目標(biāo)串t里的匹配，可以寫(xiě)：i=matching_KMP(t,p,gen_pnext(p))上述pnext的生成算法還可以改進(jìn)，下面討論生成pnext表：改進(jìn)設(shè)置pnext[i]時(shí)有一點(diǎn)情況可以考慮：t0…tj-i-1p0…pj-1tj…p0…pi-1pi…‖‖在pi

tj時(shí)（假設(shè)pnext[i]=k），如果發(fā)現(xiàn)pi=pk，那么一定pk

tj。所以模式串應(yīng)右移到

pnext[k]，下一步用

pnext[k]與

tj比較改造的算法只有循環(huán)體最后的語(yǔ)句不同：defgen_pnext(p):i,k,m=0,-1,len(p)pnext=[-1]*mwhilei<m-1:#生成下一個(gè)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表：復(fù)雜性算法復(fù)雜性的主要因素是循環(huán)與KMP主算法的分析類似：i值遞增，但不超過(guò)p的長(zhǎng)度m，說(shuō)明大循環(huán)體執(zhí)行m次i加一時(shí)k也加一，說(shuō)明k值加一m次內(nèi)層循環(huán)執(zhí)行總導(dǎo)致k值減小，但不會(huì)小于–1上面情況說(shuō)明循環(huán)體的執(zhí)行次數(shù)為O(m)，算法復(fù)雜性也是O(m)KMP算法包括pnext表構(gòu)造和實(shí)際匹配，O(m+n)。通常情況m<<n，因此可認(rèn)為算法復(fù)雜性為O(n)。顯然優(yōu)于O(m*n)KMP算法KMP算法的一個(gè)重要優(yōu)點(diǎn)是執(zhí)行中不回溯。在處理從外部（外存/網(wǎng)絡(luò)等）獲取的文本時(shí)這種特性特別有價(jià)值，因?yàn)榭梢砸贿呑x一邊匹配，不回頭重讀就不需要保存被匹配串KMP算法的優(yōu)勢(shì)KMP算法特別適合需要多次使用一個(gè)模式串的情況和存在許多匹配的情況（如在大文件里反復(fù)找一個(gè)單詞）相應(yīng)pnext表只需建立一次。這種情況下可以考慮定義一個(gè)模式類型，將pnext表作為模式的一個(gè)成分人們還提出了其他的模式匹配算法（參看wiki）另一經(jīng)典算法由Boyer和Moore提出，采用自右向左的匹配方式。如果字符集較大且匹配很罕見(jiàn)（許多實(shí)際情況如此，如在文章里找單詞，在郵件里找垃圾過(guò)濾關(guān)鍵字），其速度可能遠(yuǎn)高于KMP算法有興趣的同學(xué)可以自己找相關(guān)材料讀一讀模式匹配問(wèn)題前面討論的串匹配基于最簡(jiǎn)單的字符比較以常規(guī)的字符串作為模式比較的一方是模式串，另一方是一個(gè)字符串的所有可能子串匹配中考察的是模式串與目標(biāo)串的所有可能子串之間的相等關(guān)系基本串匹配有很廣泛的應(yīng)用，前面舉過(guò)一些例子，如正文編輯器中最常用的操作是查找和替換網(wǎng)絡(luò)搜索引擎，基本功能就是在網(wǎng)頁(yè)中檢查檢索串的匹配實(shí)際使用中，存在著許多不同的場(chǎng)景，如用一個(gè)模式串，在目標(biāo)串里反復(fù)檢索，找出一些或者所有出現(xiàn)在一個(gè)目標(biāo)串里檢查是否出現(xiàn)了一組模式串中的任何一個(gè)在一批目標(biāo)串里檢查一個(gè)或一組模式串是否出現(xiàn)，等等模式匹配的進(jìn)一步問(wèn)題實(shí)際中還經(jīng)常需要（希望）考慮一些更一般的問(wèn)題，例如一個(gè)目錄下所有以.py結(jié)尾的文件名文件里所有形為href="…"的段（HTML網(wǎng)頁(yè)里的網(wǎng)頁(yè)鏈接）DNA片段里以某堿基段開(kāi)始以另一堿基段結(jié)束的片段計(jì)算機(jī)可執(zhí)行文件中的某種片段模式（例如檢查病毒），以一種形式的片段開(kāi)始到另一片段結(jié)束，其中出現(xiàn)了某些片段等等這種匹配中考慮的不是一個(gè)字符串，而是一集字符串可能有窮，也可能無(wú)窮羅列（枚舉）的方式不適合這里的需要，因?yàn)榭赡芎芏嗷驘o(wú)窮多要處理這種匹配問(wèn)題，就需要考慮字符串集合的描述問(wèn)題，以及是否屬于一個(gè)字符串集合的匹配問(wèn)題模式匹配的進(jìn)一步問(wèn)題有關(guān)字符串集合的描述和匹配，需要考慮兩個(gè)問(wèn)題：怎樣描述被考慮的那個(gè)串集合？需要一種嚴(yán)格描述方式，能描述很多（所有？）有用的字符串集合?！跋到y(tǒng)化的”描述方式就是一種描述串檢索模式的語(yǔ)言（簡(jiǎn)單串匹配的“模式語(yǔ)言”就是字符串本身）如何（或，是否可能）高效實(shí)現(xiàn)所希望的檢查（匹配）模式描述語(yǔ)言的功能很強(qiáng)，就可能描述更多更復(fù)雜的模式（對(duì)應(yīng)的，字符串集合），但匹配算法的復(fù)雜性也會(huì)提高。這方面有許多理論結(jié)果模式語(yǔ)言變得比較復(fù)雜以后，或許只能做出具有指數(shù)復(fù)雜性的匹配算法，這種情況使模式語(yǔ)言變得沒(méi)有實(shí)用意義如果模式語(yǔ)言進(jìn)一步復(fù)雜，模式匹配問(wèn)題甚至可能變?yōu)椴豢捎?jì)算問(wèn)題。也就是說(shuō)，根本不可能寫(xiě)出完成匹配的算法。這樣的描述語(yǔ)言就完全沒(méi)有實(shí)際價(jià)值了有意義的模式描述語(yǔ)言是描述能力和處理效率之間的合理平衡模式匹配的進(jìn)一步問(wèn)題如果大家對(duì)DOS操作系統(tǒng)或者Windows命令窗口（cmd）有些了解，可能會(huì)知道描述文件名的“通配符”在Windows系統(tǒng)里搜索文件，也會(huì)用到Windows/DOS的文件名描述中可以使用兩個(gè)通配符*和?寫(xiě)在文件名字符串里的?可以與任何實(shí)際字符匹配*可與任意一串字符匹配例：*.py與所有以py為擴(kuò)展名的文件名匹配在普通字符串的基礎(chǔ)上增加通配符，形成了一種功能更強(qiáng)的模式語(yǔ)言一個(gè)模式描述一集字符串，例如a?b描述所有3個(gè)字符的串，其首字符為a，尾字符為b，中間字符任意能描述無(wú)窮字符串集合，例如a*描述了所有以a開(kāi)頭的字符串但，只是加入了通配符的模式語(yǔ)言還不夠靈活（描述能力不夠強(qiáng)）正則表達(dá)式一種很有意義的實(shí)用模式語(yǔ)言是正則表達(dá)式（RegularExpression,或稱regex、regexp、RE、re），由邏輯學(xué)家Kleene提出一個(gè)具體的正則表達(dá)式，描述字符集上的一個(gè)字符串集合正則表達(dá)式語(yǔ)言的基本成分是字符集里的普通字符，另外還有幾種特殊的組合結(jié)構(gòu)（以及表示組合的括號(hào)）正則表達(dá)式里的普通字符只與該字符本身匹配順序組合：若

匹配s，

匹配t，那么匹配st選擇組合|：若

匹配s，

匹配t，

|匹配s也匹配t星號(hào)*：與0段或者任意多段與

匹配的序列的拼接串匹配例：abc只與串a(chǎn)bc匹配a(b*)(c*)與所有一個(gè)a之后任意個(gè)b再后任意個(gè)c的串匹配a((b|c)*)與所有一個(gè)a后任意個(gè)b和c組成的序列匹配正則表達(dá)式這里不需要通配符通配符?可以用|描述（由于字符集是有窮集）通配符*可以通過(guò)|和星號(hào)描述正則表達(dá)式在實(shí)際的信息處理中非常有用人們以各種形式將其納入編程語(yǔ)言或者語(yǔ)言的標(biāo)準(zhǔn)庫(kù)存在很多不同設(shè)計(jì)，它們都是理論的正則表達(dá)式的子集或變形，基于對(duì)易用性和實(shí)現(xiàn)效率等方面的考慮，還可能有些擴(kuò)充許多腳本語(yǔ)言提供正則表達(dá)式功能，一些常規(guī)語(yǔ)言正在或計(jì)劃把正則表達(dá)式納入標(biāo)準(zhǔn)庫(kù)，C/C++/Java等語(yǔ)言也有正則表達(dá)式包經(jīng)過(guò)在Perl語(yǔ)言里的精煉，基本形成了一套比較標(biāo)準(zhǔn)的形式可以看到許多有關(guān)正則表達(dá)式的書(shū)籍或文章，把正則表達(dá)式說(shuō)成是程序員必備的重要武器，等等。網(wǎng)上的討論很熱鬧，有若干書(shū)籍正則表達(dá)式有關(guān)書(shū)籍Python正則表達(dá)式Python的正則表達(dá)式功能由標(biāo)準(zhǔn)包re提供。正則表達(dá)式可以幫助我們實(shí)現(xiàn)一些復(fù)雜的字符串操作。正確使用這個(gè)包需要理解正則表達(dá)式的描述規(guī)則和效用理解使用正則表達(dá)式的各種方法正則表達(dá)式采用Python字符串的形式描述（引號(hào)括起的字符序列）在用于一些特殊的操作時(shí)，一個(gè)具有正則表達(dá)式形式的字符串代表一種字符串模式，它能與特定的一集字符串匹配正則表達(dá)式的描述形式實(shí)際上構(gòu)成一種特殊的“小語(yǔ)言”語(yǔ)法：re規(guī)定的特殊描述規(guī)則語(yǔ)義：一個(gè)正則表達(dá)式所描述的那一集字符串Python文檔HOWTO里有一節(jié)RegularExpressionHOWTO。網(wǎng)上有些介紹Python正則表達(dá)式的網(wǎng)頁(yè)，一些Python書(shū)籍里有討論原始字符串在介紹Python正則表達(dá)式前，先介紹原始字符串（文字量）的概念原始字符串（rawstring）是Python里一種寫(xiě)字符串文字量的形式，其值（和普通文字量一樣）就是str類型的對(duì)象原始字符串的形式是在普通字符串文字量前加r或R前綴，如R"abcdefg"r"C:\courses\pathon\progs"原始字符串里的\不作為換意符，在相應(yīng)str對(duì)象里原樣保留除了位于單/雙引號(hào)前的反斜線符號(hào)引入原始字符串機(jī)制，只是為了使一些字符串的寫(xiě)法簡(jiǎn)單r"C:\courses\pathon\progs"的等價(jià)寫(xiě)法是：

"C:\\courses\\pathon\\progs"寫(xiě)模式匹配正文里的\時(shí)情況更麻煩，匹配一個(gè)\需要寫(xiě)\\\\有關(guān)詳情見(jiàn)Python文檔的HOWYO。后面將提到兩個(gè)常用情況正則表達(dá)式Python正則表達(dá)式包re規(guī)定了一組特殊字符，稱為“元字符”。它們?cè)谄ヅ渥址畷r(shí)起著特殊的作用。這種字符一共14個(gè).^$*+?\|{}[]()

注意：這些字符在（常規(guī)）字符串里都是普通字符（“\”除外），只有在把字符串作為正則表達(dá)式使用時(shí)，它們有特殊的意義非特殊字符稱為常規(guī)字符，是描述正則表達(dá)式的基礎(chǔ)正則表達(dá)式串里的常規(guī)字符在匹配中只與自己匹配如果一個(gè)正則表達(dá)式串只包含常規(guī)字符，它就只能與自己匹配。也就是說(shuō)，常規(guī)字符串是最基本的正則表達(dá)式在介紹正則表達(dá)式元字符的使用之前，先介紹re包提供的幾個(gè)操作可以通過(guò)這些操作去使用正則表達(dá)式（還有其他方式，后面介紹）在下面函數(shù)說(shuō)明中，參數(shù)表里的pattern

表示描述正則表達(dá)式的字符串（模式串），string

表示被處理的字符串，repl

表示替換串正則表達(dá)式生成正則表達(dá)式對(duì)象：pile(pattern,flag=0)從pattern生成對(duì)應(yīng)的正則表達(dá)式對(duì)象。可用于下面幾個(gè)操作。例：r1=pile("abc")生成"abc"對(duì)應(yīng)的正則表達(dá)式對(duì)象賦給變量r1re包的操作都有flag選項(xiàng)。re專門提供了一組特殊標(biāo)記，這里不考慮實(shí)際上，下面幾個(gè)操作都能自動(dòng)從pattern串生成正則表達(dá)式對(duì)象。用compile生成對(duì)象并記入變量，可以避免在重復(fù)使用中重復(fù)生成。下面函數(shù)的pattern參數(shù)都可以用正則表達(dá)式串或?qū)ο笞鳛閷?shí)參檢索：re.search(pattern,string,flag=0)在string

里檢索與pattern

匹配的子串。如找到就返回一個(gè)match類型的對(duì)象；沒(méi)找到時(shí)返回Nonematch對(duì)象里記錄成功匹配的相關(guān)信息，可以根據(jù)需要取出和使用。也可以簡(jiǎn)單地把它作為一個(gè)真值用于邏輯判斷正則表達(dá)式匹配：re.match(pattern,string,flag=0)檢查string是否有與pattern匹配的前綴，匹配成功時(shí)返回相應(yīng)的match對(duì)象，否則返回None。例：re.search(r1,"aaabcbcbabcb")成功，但re.match(r1,"aaabcbcbabcb")返回None分割：re.split(pattern,string,maxsplit=0,flags=0)以pattern作為分割串將string分段，maxsplit指明分割數(shù)，0表示做完整個(gè)string。函數(shù)返回分割得到的字符串的表。例

re.split('',"abcabbarenotthesame")

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

re.split("","1234")#分割出了幾個(gè)空串

得到：['1','2','','3','','','4']正則表達(dá)式找到所有匹配串：re.findall(pattern,string,flags=0)本函數(shù)返回一個(gè)表，其元素按順序給出string里與pattern匹配的（從左到右非重疊的）各個(gè)子串如果模式里只有常規(guī)字符，做這種匹配的價(jià)值不大，因?yàn)榻Y(jié)果表里所有的字符串相同。但用一般的正則表達(dá)式模式，情況就會(huì)不同還有操作后面介紹，下面逐步介紹正則表達(dá)式的情況。正則表達(dá)式的描述如前所說(shuō)，Python標(biāo)準(zhǔn)庫(kù)包re的正則表達(dá)式就是一類特殊形式的字符串，可用于re里定義的一些函數(shù)，完成一些字符串操作正則表達(dá)式的最基本組合是順序組合，若

匹配s，

匹配t，那么匹配s+t（s,t為字符串，Python寫(xiě)法s+t是兩個(gè)字符串的拼接）注意，在正則表達(dá)式里，同樣可以（也常常需要）寫(xiě)普通Python字符串使用的換意字符，如\n表示換行，\t表示制表符等正則表達(dá)式里的空格也是常規(guī)字符，它只與自己匹配下面分門別類介紹一些特殊的描述形式，需要注意兩點(diǎn)：一種表達(dá)式（或元符號(hào)）的構(gòu)造形式（描述形式）這種表達(dá)式能匹配怎樣的字符串（集合）字符組字符組表達(dá)式[...]匹配括號(hào)中列出的任一個(gè)字符[abc]

可以匹配字符a或b或c區(qū)間形式[0-9]是順序列出的縮寫(xiě)，匹配所有十進(jìn)制數(shù)字字符[0-9a-zA-Z]

匹配所有字母（英文字母）和數(shù)字[^...]中的^表示求補(bǔ)，這種模式匹配所有未在括號(hào)里列出的字符[^0-9]匹配所有非十進(jìn)制數(shù)字的字符[^\t\v\n\f\r]

匹配所有非空白字符（非空格/制表符/換行符）如果需要在字符組里包括^，就不能放在第一個(gè)位置，或者寫(xiě)\^；如果需要在字符組包括-

]，也必須寫(xiě)\-或\]圓點(diǎn)字符.匹配任意一個(gè)字符a..b匹配所有以a開(kāi)頭b結(jié)束的四字符串a(chǎn)[1-9][0-9]匹配a10,a11,...,a99常用字符組為了方便，re用換意串形式定義了幾個(gè)常用字符組，包括：\d：與十進(jìn)制數(shù)字匹配，等價(jià)于[0-9]\D：與非十進(jìn)制數(shù)字的所有字符匹配，等價(jià)于[^0-9]\s：與所有空白字符匹配，等價(jià)于[\t\v\n\f\r]\S：與所有非空白字符匹配，等價(jià)于[^\t\v\n\f\r]\w：與所有字母數(shù)字字符匹配，等價(jià)于[0-9a-zA-Z]\W：與所有非字母數(shù)字字符匹配，等價(jià)于[^0-9a-zA-Z]還有些類似描述，提供這些只是為了使用方便p\w\w\w與p開(kāi)頭隨后三個(gè)字母數(shù)字字符的串匹配重復(fù)常希望寫(xiě)重復(fù)匹配的模式（部分），任意次或若干次重復(fù)基本重復(fù)運(yùn)算符是*，*與

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

將串按空格和逗號(hào)（任意個(gè)）切分re.split('[,]*','12,34,,5')

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

得到['','bb','bbdbb','bb','b','bb','bb']注意，re.match('ab*','abbbbbbc')時(shí)，模式可以與a匹配，與ab匹配，等等，它究竟匹配那個(gè)串？?jī)煞N可能貪婪匹配：與有可能匹配的最長(zhǎng)子串匹配在這里ab*匹配abbbbbb，*運(yùn)算符做貪婪匹配非貪婪匹配：與有可能匹配的最短子串匹配重復(fù)與*略微不同的重復(fù)運(yùn)算符+表示1次或多次重復(fù)例：描述正整數(shù)的一種簡(jiǎn)單模式'\d+'，等價(jià)于'\d\d*'可選（片段）用?運(yùn)算符表示?

表示0次或1次重復(fù)例，描述整數(shù)（表示整數(shù)的字符串）的一種簡(jiǎn)單模式'-?\d+'確定次數(shù)的重復(fù)用{n}表示，{n}與

匹配的串的n次重復(fù)匹配描述北京常規(guī)的固話號(hào)碼：'(010-)?[2-9][0-9]{7}'注意：這種表達(dá)式描述的通常是實(shí)際字符串集合的超集，但可以用注意：上面描述中出現(xiàn)了圓括號(hào)，描述?的作用范圍*,?,{3}

有作用范圍問(wèn)題（優(yōu)先級(jí)），它們作用于最小表達(dá)式'010-?'表示其中的'–'可選，'(010-)?'表示整個(gè)段可選重復(fù)重復(fù)范圍用{m,n}表示，{m,n}與

匹配的串的m到n次重復(fù)匹配a{3,7}與3到7個(gè)a構(gòu)成的串匹配go{2,10}gle與google,gooogle,...,goooooooooogle匹配重復(fù)范圍中的m和n均可以省略，{,n}表示{0,n}，而{m,}表示{m,infinity}。另外幾種重復(fù)都可以用這個(gè)形式表示：{n}等價(jià)于{n,n}，?等價(jià)于{0,1}*等價(jià)于{0,infinity}，+等價(jià)于{1,infinity}*+?{m,n}

都采取貪婪匹配策略，與被匹配串中最長(zhǎng)的合適子串匹配（因?yàn)樗鼈兛赡艹霈F(xiàn)更大的模式里，要照顧上下文的需要）與這些運(yùn)算符對(duì)應(yīng)的有一組非貪婪匹配運(yùn)算符*?+???{m,n}?（各運(yùn)算符后增加一個(gè)問(wèn)號(hào)）的語(yǔ)義與上面幾個(gè)運(yùn)算符分別對(duì)應(yīng)，但采用非貪婪匹配（最小匹配）的策略選擇選擇運(yùn)算符|描述兩種或多種情況之一的匹配。如果

或者與一個(gè)串匹配，那么

|就與之匹配a|b|c

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

可以看作其簡(jiǎn)寫(xiě)。后者更簡(jiǎn)潔方便，有時(shí)還能簡(jiǎn)寫(xiě)如[a-z]，但只能用于單字符選擇'0+|[1-9]\d*'

匹配Python程序的十進(jìn)制整數(shù)（注意，Python把負(fù)號(hào)看作運(yùn)算符）。如果已知為獨(dú)立字段，就可以用這個(gè)模式。但它會(huì)與0123的前段0匹配。進(jìn)一步考慮還有上下文要求（如需排除abc123,

a123b里的123），這方面的問(wèn)題后面考慮|的結(jié)合力最弱，比順序組合還弱。上面描述不需要括號(hào)實(shí)例：匹配國(guó)內(nèi)固定電話號(hào)碼：'0\d{2}-\d{8}|0\d{3}-\d{7,8}'注意，這個(gè)正則表達(dá)式描述的是實(shí)際集合的超集，如兩位區(qū)號(hào)實(shí)際上只有010/020/021/022，這段可寫(xiě)為

0(10|20|21|22|23)-\d{8}，另一段可以精化為0[3-9]\d{2}-\d{7,8}首尾匹配行首匹配：以^符號(hào)開(kāi)頭的模式，只能與一行的前綴子串匹配re.search('^for','booksforchildren')得到None行尾匹配：以$符號(hào)結(jié)尾的模式，只與一行的后綴匹配re.search('fish$','catsliketoeatfishes')得到None注意，“一行的”前綴/后綴包括整個(gè)被匹配串的前綴和后綴。如串里有換行符，還包括換行符前的子串（一行的后綴）和其后的子串（前綴）串首匹配：\A開(kāi)頭的模式只與被匹配串的前綴匹配串尾匹配：\Z結(jié)束的模式只與被匹配串的后綴匹配至此我們已經(jīng)介紹了所有14個(gè)元字符應(yīng)特別提出換意字符\，以它作為引導(dǎo)符定義了一批換意元字符，如\d,\D

等。它還用于在模式串里寫(xiě)非打印字符（如\t,\n,...）和\\等，在[]里寫(xiě)\^,\-,\]單詞邊界兩個(gè)換意元字符用于描述特殊子串的邊界\b描述單詞邊界，它表示單詞邊界匹配一個(gè)空串。單詞是字母數(shù)字的連續(xù)序列，邊界就是非字母數(shù)字字符或無(wú)字符（串開(kāi)頭/結(jié)束）這里有個(gè)糟糕的問(wèn)題：在Python字符串中\(zhòng)b表示退格符，而在re的正則表達(dá)式里\b表示單詞邊界。兩種辦法：將\雙寫(xiě)，它表示把\本身送給pile，如'\\b123\\b'不匹配abc123a等里的123，但匹配(123,123)里的123用Python原始字符串，其中的\不換意。上面的模式可寫(xiě)為r'\b123\b'實(shí)例：匹配Python整數(shù)的模式可寫(xiě)為'\\b(0+|[1-9]\d*)\\b'用原始字符串可簡(jiǎn)單地寫(xiě)r'\b(0+|[1-9]\d*)\b'。例如寫(xiě) re_int=r'\b(0+|[1-9]\d*)\b'單詞邊界實(shí)例：一般的可能帶正負(fù)號(hào)的整數(shù)，可以考慮用模式'[+-]?\\b(0+|[1-9]\d*)\\b'但它匹配x+5

里的+5，但不匹配3+-5里的-5。寫(xiě)這種表達(dá)式和使用時(shí)，都需要考慮被匹配對(duì)象的情況例：求一個(gè)Python程序里出現(xiàn)的所有整數(shù)之和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的補(bǔ)，也是匹配空串，但要求相應(yīng)位置是字母或數(shù)字實(shí)例：>>>re.findall('py.\B','python,py2,py342,py1py2py4')['pyt','py3','py1','py2']匹配對(duì)象（match對(duì)象）許多匹配函數(shù)在匹配成功時(shí)返回一個(gè)match對(duì)象，對(duì)象里記錄了所完成匹配的有關(guān)信息，可以取出使用。下面介紹這方面的情況首先，這樣的匹配結(jié)果可以用于邏輯判斷，成功時(shí)得到的match對(duì)象總表示邏輯真，不成功得到的None表示假。例如match1=re.search(pt,text)ifmatch1:...match1...text...#使用match對(duì)象的處理操作match對(duì)象提供了一組方法，用于檢查與匹配有關(guān)的信息。下面介紹一些基本用法，更多信息（包括可選參數(shù)）見(jiàn)re包文檔在下面介紹中，mat

表示通過(guò)匹配得到的一個(gè)match對(duì)象取得被匹配的子串：mat.group()在一次成功匹配中，所用的正則表達(dá)式匹配了目標(biāo)串的一個(gè)子串，操作mat.group()給出這個(gè)子串匹配對(duì)象（match對(duì)象）在目標(biāo)串里的匹配位置：mat.start()得到mat

代表的成功匹配在目標(biāo)串里的實(shí)際匹配位置，這是目標(biāo)串的一個(gè)字符位置（下標(biāo)）目標(biāo)串里被匹配子串的結(jié)束位置：mat.end()這個(gè)位置采用常規(guī)表示方式。設(shè)text是目標(biāo)串，有如下關(guān)系：mat.group()==text[mat.start():mat.end()]目標(biāo)串里被匹配的區(qū)間：mat.span()得到匹配的開(kāi)始和結(jié)束位置形成的二元組mat.span()==mat.start(),mat.end()mat.re和mat.string分別取得得到這個(gè)match對(duì)象所做匹配的正則表達(dá)式對(duì)象和目標(biāo)串應(yīng)用實(shí)例見(jiàn)后模式里的組（group）正則表達(dá)式描述中的另一個(gè)重要概念是組（group）圓括號(hào)括起的模式段(...)也是模式，它與被括子模式匹配的串匹配。但在此同時(shí)還確定了一個(gè)被匹配的“組”（字符段）成功匹配得到的組從0開(kāi)始編號(hào)，可以通過(guò)mat.group(n)獲取組0就是整個(gè)模式匹配的串，用mat.group()獲得（默認(rèn)參數(shù)）模式里每對(duì)圓括號(hào)確定一個(gè)組，按開(kāi)括號(hào)的順序編號(hào)，例如m=re.search('.((.)e)f','abcdef')#執(zhí)行后：m.group()是'cdef'，m.group(1)是'de'，m.group(2)是'd'm.groups()得到包含從編號(hào)1開(kāi)始的各組的序?qū).groups()得到('de','d')成功匹配確定的各個(gè)組可用\n

形式在模式里其他地方“引用”，表示要求在這個(gè)位置匹配同一個(gè)子串。這里的n表示一個(gè)整數(shù)序號(hào)模式里的組例：r'(.{2})\1'

可匹配'okok'

或'nono'，不匹配'nooh'注意，組編號(hào)應(yīng)該是\1,\2等，但在普通字符串里，\1表示二進(jìn)制編碼為1（經(jīng)?？梢钥吹奖粚?xiě)成0x01）的那個(gè)（特殊）字符，而現(xiàn)在需要模式串里出現(xiàn)\1,\2等為此上面模式需要寫(xiě)成'(.{2})\\1'，或者用原始字符串形式簡(jiǎn)化寫(xiě)法，寫(xiě)為r'(.{2})\1'(?...)形式的片段稱為“擴(kuò)充表示”，