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

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

為s2

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

是s2

的子串，也說s1

在s2

里出現(xiàn)，稱s2

里與s1

相同的字符段的第一個字符的位置為s1

在s2

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

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

相同的段，這時說s1

在s2

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

為s2

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

為s2

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

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

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

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

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

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

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

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

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

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

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

是字符）

t=t0t1t2…tn-1

稱為目標(biāo)串

p=p0p1p2…pm-1

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

t

a

b

b

b

a

a

p

a

b

a

a

b

a

a

b

a

a

b

a

串匹配的樸素算法樸素的串匹配算法的一個實現(xiàn)：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:#找到匹配,返回其開始下標(biāo)

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

失敗（設(shè)遇到pi

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

去與tj

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

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

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

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

的匹配）。也就是說：tj

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

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

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

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

值特殊情況：在pi

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

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

與tj+1

比較。遇到這種特殊情況就在pnext[i]里記錄–1顯然，對任何模式都有：pnext[0]=-1KMP算法假設(shè)已經(jīng)根據(jù)模式串p做出了pnext表，考慮KMP算法的實現(xiàn)匹配循環(huán)很容易寫出，如下：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算法匹配函數(shù)的定義：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:#找到匹配,返回其下標(biāo)

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

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

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

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

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

最長相等前后綴（不包括p0…pi-1

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

tj

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

與tj也就是說，應(yīng)該把pnext[i]設(shè)置為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中對應(yīng)那些字符匹配，而這實際上也就是與pi-k…pi-1匹配KMP算法：生成pnext表利用已知pnext[0]=-1直至pnext[i]求pnext[i+1]的算法：假設(shè)next[i]=k。若pk=pi，則p0…pi-k…pi

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

pi

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

中最大相同前后綴的長度為0，設(shè)pnext[i+1]=0，將i值加一后繼續(xù)遞推針對i遞推計算最長相等前后綴的長度。設(shè)對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的最長相同前綴移過來繼續(xù)檢查KMP算法：生成pnext表生成pnext表的Python函數(shù)定義defgen_pnext(p):i,k,m=0,-1,len(p)pnext=[-1]*m#初始數(shù)組元素全為-1whilei<m-1:#生成下一個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里的匹配，可以寫：i=matching_KMP(t,p,gen_pnext(p))上述pnext的生成算法還可以改進，下面討論生成pnext表：改進設(shè)置pnext[i]時有一點情況可以考慮：t0…tj-i-1p0…pj-1tj…p0…pi-1pi…‖‖在pi

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

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

pnext[k]，下一步用

pnext[k]與

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

匹配s，

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

匹配s，

匹配t，

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

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

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

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

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

表示被處理的字符串，repl

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

里檢索與pattern

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

re.split('',"abcabbarenotthesame")

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

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

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

匹配s，

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

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

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

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

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

的0次或任意多次出現(xiàn)匹配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，*運算符做貪婪匹配非貪婪匹配：與有可能匹配的最短子串匹配重復(fù)與*略微不同的重復(fù)運算符+表示1次或多次重復(fù)例：描述正整數(shù)的一種簡單模式'\d+'，等價于'\d\d*'可選（片段）用?運算符表示?

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

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

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

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

都采取貪婪匹配策略，與被匹配串中最長的合適子串匹配（因為它們可能出現(xiàn)更大的模式里，要照顧上下文的需要）與這些運算符對應(yīng)的有一組非貪婪匹配運算符*?+???{m,n}?（各運算符后增加一個問號）的語義與上面幾個運算符分別對應(yīng)，但采用非貪婪匹配（最小匹配）的策略選擇選擇運算符|描述兩種或多種情況之一的匹配。如果

或者與一個串匹配，那么

|就與之匹配a|b|c

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

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

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

a123b里的123），這方面的問題后面考慮|的結(jié)合力最弱，比順序組合還弱。上面描述不需要括號實例：匹配國內(nèi)固定電話號碼：'0\d{2}-\d{8}|0\d{3}-\d{7,8}'注意，這個正則表達式描述的是實際集合的超集，如兩位區(qū)號實際上只有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行尾匹配：以$符號結(jié)尾的模式，只與一行的后綴匹配re.search('fish$','catsliketoeatfishes')得到None注意，“一行的”前綴/后綴包括整個被匹配串的前綴和后綴。如串里有換行符，還包括換行符前的子串（一行的后綴）和其后的子串（前綴）串首匹配：\A開頭的模式只與被匹配串的前綴匹配串尾匹配：\Z結(jié)束的模式只與被匹配串的后綴匹配至此我們已經(jīng)介紹了所有14個元字符應(yīng)特別提出換意字符\，以它作為引導(dǎo)符定義了一批換意元字符，如\d,\D

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

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

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

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

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

可匹配'okok'

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