3，字符串字符串的相關概念Python字符串（回顧）字符串匹配和算法進一步的模式匹配問題正則表達式Python的正則表達式應用舉例數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/字符串數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/討論字符串，首先要有一個確定的字符集?“字符”是一個抽象概念，字符集是有窮的一組字符構成的集合?人們經常考慮在計算機里使用的標準字符集，實際上，完全可以拿任意數據元素的集合作為字符集字符串（簡稱串）是特殊的線性表，表中元素取自選定的字符集 其不同于一般表的特點是支持一組以串為對象的操作長度：串中字符的個數稱為串的長度?長度為0的串稱為空串?在任意一個字符集里，只有唯一的一個空串與一般的表類似：?字符串里的字符順序排列，串里的每個字符有其確定位置?我們用0開始的自然數表示位置字符串數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/串相等：串的相等基于字符集里的字符定義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里拼接運算用+表示字符串數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/兩個串之間還有一個重要的關系是“子串關系”稱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也都是該串本身的子串字符串數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/兩種特殊子串：?如果存在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語言）字符串的理論數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/字符串集合和拼接操作構成了一種代數結構?空串是拼接操作的“單位元”（幺元）有結合律，無交換律?串集合加上拼接操作，構成一個半群一種典型的非交換半群?有單位元，因此是一個幺半群關于串的理論有許多研究工作?基于串和串替換，研究者提出了post系統這是一種與圖靈機等價的計算模型?（串）重寫系統（rewritingsystem）是計算機理論的一個研究領域，一直非常活躍，有許多重要結果和應用字符串抽象數據類型數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/可以考慮下面的字符串抽象數據類型：ADT

String: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在串里的出現子串檢索（子串匹配）是字符串的核心操作，后面將詳細研究字符串的實現數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/串是字符的線性序列：?可采用線性表的實現方式，用順序表示和鏈接表示。例如用能動態變化大小的順序表作為實現方式（如果需要表示可變的字符串）?還可以根據串本身的特點和串操作的特點，考慮其他表示方式。當然，無論如何還是基于順序存儲或/和鏈接?關鍵問題：表示方式應能很好支持串的管理和相關操作的實現字符串表示的兩個問題：?串內容存儲。兩個極端：1，連續存儲在一塊存儲區；2，一個字符存入一個獨立存儲塊，鏈接起來。也可以采用某種中間方式，把串中字符分段保存在一組存儲塊里，鏈接起這些存儲塊?串結束的表示，不同字符串長度可能不同，必須表示串到哪里結束。兩種基本方式：1，用專門數據域記錄字符串長度；2，用一個特殊

符號表示串結束（例如C語言的字符串采用這種方式）字符串的實現數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/現在考慮字符串的操作許多串操作是線性表操作的具體實例，包括串拼接下面考慮一個特殊的操作串替換?牽涉到三個串：被處理的主串s，作為被替換對象需要從s中替換掉的子串t，以及用于代換t的t"?由于t可能在s中出現多次，因此需要通過一系列具體的子串代換完成整個替換?由于多次出現可能重疊（回憶前面的例子），只能規定一種代換順序（例如從左到右），一次代換破壞的子串不應再代入新串?一次子串代換后，應該從代入的新串之后繼續工作。即使代入新串之后形成的部分能與t匹配，也不應在本次替換中考慮?很容易看到：串替換的關鍵是找到匹配實際語言里的字符串數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/許多語言提供了標準的字符串功能，如?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找子串位置等。這類操作最重要，后面專門討論數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/字符串操作的實現檢查字符串內容的操作可以分為兩類?O(1)時間的簡單操作，包括len和定位訪問（也構造新字符串）?其他都需要掃描整個串的內容，包括不變序列的共有操作（in、not

in、min/max），各種字符類型判斷（如是否全為數字）需通過一個循環逐個檢查串中字符完成工作，O(n)操作子串查找和匹配的問題后面討論需要構造新字符串的操作情況比較復雜，基本模式都包括兩部分工作

1,為新構造的串安排一塊存儲2,根據被操作串（和可能的參數串）構造出一個新串以s[a:b:k]為例，算法：1,根據a、b、k算出新字符串的長度2,for

i

in

range(a,b,k):拷貝s[i]到新串里的下一個空位數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/字符串匹配（子串查找）數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

最重要的字符串操作是子串匹配，稱為字符串匹配（stringmatching）或字符串查找（string

searching）【有教科書稱為模式匹配（pattern

match），但實際上模式匹配是內涵更廣的概念】wiki：/wiki/String_searching_algorit字符串匹配問題：假設有兩個串（ti,pj

是字符）t

=

t0

t1

t2

…

tn-1p

=

p0

p1

p2

…

pm-1稱為目標串稱為模式串通常有m<<n。字符串匹配就是在t中查找與等于p的子串的過程（這一定義可以推廣，后面討論）

如前所述，串匹配是最重要的字符串操作，也是其他許多重要字符串操作的基礎。實際中n可能非常大，m也可以有一定規模，也可能需要做許多模式串和/或許多目標串的匹配，有關算法的效率非常重要串匹配數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/許多計算機應用的最基本操作是字符串匹配。如?用編輯器或字處理系統工作時，在文本中查找單詞或句子（中文字或詞語），在程序里找拼寫錯誤的標識符等?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分析）數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/串匹配和算法數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/還需注意不同的實際需要，如?用一個模式在很長的目標串里反復匹配（確定出現位置）?一組（可能很多）模式，在一個或一組目標串里確定是否有匹配不同算法在處理不同實際情況時可能有不同的表現人們已經開發出一批有意義的（有趣）算法（進一步情況見wiki）粗看，字符串匹配是一個很簡單的問題?字符串是簡單數據（字符）的簡單序列，結構也最簡單（順序）?很容易想到最簡單而直接的算法?但事實是：直接而簡單的算法并不是高效的算法因為它可能沒有很好利用問題的內在結構?字符串匹配貌似簡單，但人們已開發出許多“大相徑庭的”算法串匹配的樸素算法串匹配的基礎是逐個比較字符?如果從目標串的某個位置開始，模式串的每個字符都與目標串里的對應字符相同，這就是一個匹配?如果出現一對不同字符，就是不匹配算法設計的關鍵：1，怎樣比較字符；2，發現不匹配后下一步怎么做?對上述兩點采用不同的策略，就形成了不同的算法?從下面兩個例子可以看到一些情況，更多實例見wiki

樸素匹配算法：1，從左到右匹配；2，發現不匹配時，考慮目標串里的下一位置是否存在匹配t

a

b

b

a

b

ap

a

ba

ab

aba

ab

a數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/串匹配的樸素算法數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/樸素的串匹配算法的一個實現：

def

naive_nmatching(t,p):m,

n

=

len(p),

len(t)i,

j

=

0,

0while

i<m

and

j<n:

#i==m說明找到了匹配if

p[i]==t[j]:

#字符相同!考慮下一對字符i,j=i+1,j+1else:

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

i==m:

#找到匹配,返回其開始下標return

j-ireturn-1

#無匹配,返回特殊值樸素匹配算法簡單，易理解，但效率低造成效率的主要操作是執行中可能出現的回溯：遇字符不等時將模式串

p右移一個字符，再次從p0

（重置j=0后）開始比較串匹配的樸素算法數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

最壞情況是每趟比較都在最后出現不等，最多比較n－m＋1趟，總比較次數為m*(n－m＋1)，所以算法時間復雜性為O(m*n)最壞情況的一個實例目標串：00000000000000000000000000000000000000001模式串：00000001樸素算法效率低的原因：把每次字符比較看作完全獨立的操作?完全沒有利用字符串本身的特點（每個字符串都是特殊的）?沒有利用前面已做過的字符比較得到的信息

從數學上看，這樣做相當于認為目標串和模式串里的字符都是隨機量，而且有無窮多可能取值，兩次字符比較相互無關也不可借鑒?實際字符串取值來自一個有窮集合?每個串都有窮。特別是模式串通常不太長，而且可能反復使用數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/無回溯匹配：KMP算法KMP算法是一個高效串匹配算法。由D.E.Knuth和V.R.Pratt提出，J.H.Morris幾乎同時發現，因此稱KMP算法。這是本課程中第一個非平凡算法，基于對問題的深入分析，算法不易理解但效率高

要理解KMP算法，首先需要了解樸素算法的缺陷。現在仔細考察樸素算法的執行過程。設目標串t:ababcabcacbab，模式串p:abcac第一趟匹配第二趟匹配第三趟匹配第四趟匹配a

b

a

b

c

a

b

c

a

c

b

a

ba

b

c

a

ca

b

a

b

c

a

b

c

a

c

b

a

ba

b

c

a

ca

b

a

b

c

a

b

c

a

c

b

a

ba

b

c

a

ca

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模式串為匹配前已知，在匹配中反復使用若先對模式串做細致分析，記錄有用信息（靜態預處理），有可能加快匹配無回溯匹配：KMP算法

KMP算法的基本想法：在匹配失敗時，利用已做匹配得到的信息，把模式串盡可能前移。匹配中只做不得不做的字符比較，不回溯處理同一個實例：第一趟匹配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

c

這里的匹配絕不回溯，如果匹配到

tj

失敗（設遇到

pi

tj），就去找到某個

pki，0

ki

<

i，下一步用

pki

去與

tj

比較

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

失敗，對相應的i，對應ki

都一樣嗎？數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/無回溯匹配：分析數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

關鍵認識：在

pi

匹配失敗時，所有

pk（0

k<

i）都已匹配成功（否則不會考慮

pi

的匹配）。也就是說：tj

之前的i-1個字符就是p的前i-1個字符！：原本應該根據t的情況確定前移方式，但實際上可以根據p本身的情況確定，可以通過對模式串本身的分析在匹配之前做好

結論：對p

中的每個i，有一個唯一確定的ki，與被匹配的串無關。通過對模式串

p

的預分析，可以得到每個

i

對應的

ki

值（

）

設

p

的長度為

m，需要對每個

i

(0

i

<

m)算出一個ki

值并保存，以便在匹配中使用。考慮把這

m

個值（i

和ki

的對應關系）存入一個表pnext，用

pnext[i]

表示與

i

對應的

ki

值

特殊情況：在pi

匹配失敗時，有可能發現用pi

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

與tj+1

比較。遇到這種特殊情況就在pnext[i]里記錄–1顯然，對任何模式都有：pnext[0]=-1KMP算法數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/假設已經根據模式串p做出了pnext表，考慮KMP算法的實現匹配循環很容易寫出，如下：while

j<n

and

i<m:

#i==m

means

a

matchingif

i==-1:

#遇到–1，比較下一對字符j,

i

=

j+1,

i+1elif

t[j]==p[i]:

#字符相等，比較下一對字符j,i=j+1,i+1else:

#從pnext取得p下一字符的位置i=pnext[i]if的前兩個分支可以合并：while

j<n

and

i<m:

#i==m

means

a

matchingif

i==-1

or

t[j]==p[i]:

#比較下一對字符j,

i

=

j+1,

i+1else:

#從pnext取得p下一字符的位置i=pnext[i]KMP算法數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/匹配函數的定義：def

matching_KMP(t,

p,

pnext):j,

i

=

0,

0n,

m

=

len(t),

len(p)while

j<n

and

i<m:

#i==m說明找到了匹配if

i==-1

or

t[j]==p[i]:

#考慮p中下一字符j,i=j+1,i+1else:

#失敗!考慮pnext決定的下一字符i=pnext[i]#找到匹配,返回其下標if

i

==

m:return

j-ireturn

-1#無匹配,返回特殊值算法復雜性的關鍵是循環。注意循環中j的值遞增，但加一的總次數不多于n=len(t)。而且j遞增時i值也遞增。另一方面i=pnext[i]總使

i值減小，但條件保證其值不小于–1，因此i=pnext[i]的執行次數不會多于i值遞增的次數。循環次數是O(n)，算法復雜性也是O(n)KMP算法：生成pnext表第二趟匹配a

b

a

b

c

a

b

c

a

c

b

a

ba

b

c

a

c(a)b

c

a

c?新位置的前綴子串應該與匹配失敗字符之前同長度的子串相同?如果在模式串匹配失敗時，前面一段里滿足上述條件的位置不止一處，只能移到最近的那個位置（保證不遺漏可能的匹配）￠

已知ki

值只依賴于p本身的前i個字符現在考慮pnext表的構造，以下面情況為例t0

…tj-i-1

tj-i…tj-1

tj…p0

…pi-1

pi…t0

…tj-i-1

p0

…pi-1

tj…i

j數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/設匹配到

p

/t

時失敗t中位置j之前的i個字符就是

p的前i個字符KMP算法：生成pnext表正確k值由

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

如果p0

…pi-1

最長相等前后綴（不包括p0

…pi-1

本身但可為空）的長度為

k

(0 k

<

i-1)。當

pi

tj

時

p

應右移

i

-

k

位，隨后比較

pk

與

tj也就是說，應該把pnext[i]設置為k

求pnext的問題變成對每個i求p的（前綴）子串p0

…pi-1

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

后綴p0

…pk-1

pk…前綴t0

…tj-i-1

p0

…pk-1

…pi-k…pi-1

t保j…證其前綴p0

…pk-1

與t中對應那數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/模式串的正確前移位置移位，必須些字符匹配，而這實際上也就是與pi-k

…pi-1

匹配KMP算法：生成pnext表針對i遞推計算最長相等前后綴的長度。設對i-1已經算出，于是pi

pi+

1p0

…

…

…

pk-1

…

pi-k…

…

…

pi-1

…？p0

…

…

…

pk-1

pk

pk+

1

…?如果pi

=pk，pnext[i]應該為k，繼續?否則把p0

...pk-1

的最長相同前綴移過來繼續檢查利用已知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值加一后繼續遞推數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/KMP算法：生成pnext表數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/生成pnext表的Python函數定義

def

gen_pnext(p):i,

k,

m

=

0,

-1,

len(p)pnext

=

[-1]

*

mwhile

i

<

m-1:#初始數組元素全為-1#生成下一個pnext元素值if

k

==

-1

or

p[i]

==

p[k]:i,

k

=

i+1,

k+1pnext[i]=k

#設置pnext元素

else:k=pnext[k]

#退到更短相同前綴return

pnext求模式串p在目標串t里的匹配，可以寫：

i=matching_KMP(t,p,gen_pnext(p))上述pnext的生成算法還可以改進，下面討論裘宗燕，5/3/2020-/1/數據結構r和e算t法ur（nPypthnoenx語t言版）：字符串生成pnext表：改進設置pnext[i]時有一點情況可以考慮：p0

…pi-1

pi…t0

…tj-i-1

p0

…pj-1

tj…在pi

jt

時（假設pnext[i]=k），如果發現pi

=

pk，那么一定

pk

tj

。所以模式串應右移到pnext[k]，下一步用pnext[k]與tj

比較改造的算法只有循環體最后的語句不同：

def

gen_pnext(p):i,

k,

m

=

0,

-1,

len(p)pnext

=

[-1]

*

mwhile

i<m-1:

#生成下一個pnext元素if

k

==

-1

or

p[i]

==

p[k]:i,

k

=

i+1,

k+1if

p[i]

==

p[k]

:pnext[i]

=

pnext[k]else:pnext[i]

=

kelse:k

=

pnext[k]生成pnext表：復雜性數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/算法復雜性的主要因素是循環 與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算法數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

KMP算法的一個重要優點是執行中不回溯。在處理從外部（外存/網絡等）獲取的文本時這種特性特別有價值，因為可以一邊讀一邊匹配，不回頭重讀就不需要保存被匹配串KMP算法的優勢?KMP算法特別適合需要多次使用一個模式串的情況和存在許多匹配的情況（如在大文件里反復找一個單詞）?相應pnext表只需建立一次。這種情況下可以考慮定義一個模式類型，將pnext表作為模式的一個成分人們還提出了其他的模式匹配算法（參看wiki）?另一經典算法由Boyer和Moore提出，采用自右向左的匹配方式。如果字符集較大且匹配很罕見（許多實際情況如此，如在文章里找單詞，在郵件里找垃圾過濾關鍵字），其速度可能遠高于KMP算法?有興趣的同學可以自己找相關材料讀一讀模式匹配問題數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/前面討論的串匹配基于最簡單的字符比較?以常規的字符串作為模式?比較的一方是模式串，另一方是一個字符串的所有可能子串?匹配中考察的是模式串與目標串的所有可能子串之間的相等關系基本串匹配有很廣泛的應用，前面舉過一些例子，如?正文編輯器中最常用的操作是查找和替換?網絡搜索引擎，基本功能就是在網頁中檢查檢索串的匹配實際使用中，存在著許多不同的場景，如?用一個模式串，在目標串里反復檢索，找出一些或者所有出現?在一個目標串里檢查是否出現了一組模式串中的任何一個?在一批目標串里檢查一個或一組模式串是否出現，等等模式匹配的進一步問題數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/實際中還經常需要（希望）考慮一些更一般的問題，例如?

一個目錄下所有以.py結尾的文件名?

文件里所有形為href="…"的段（HTML網頁里的網頁鏈接）?

DNA片段里以某堿基段開始以另一堿基段結束的片段?

計算機可執行文件中的某種片段模式（例如檢查病毒），以一種形式的片段開始到另一片段結束，其中出現了某些片段?

等等這種匹配中考慮的不是一個字符串，而是一集字符串?

可能有窮，也可能無窮?

羅列（枚舉）的方式不適合這里的需要，因為可能很多或無窮多?

要處理這種匹配問題，就需要考慮字符串集合的描述問題，以及是否屬于一個字符串集合的匹配問題模式匹配的進一步問題數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/有關字符串集合的描述和匹配，需要考慮兩個問題：怎樣描述被考慮的那個串集合？需要一種嚴格描述方式，能描述很 多（所有？）有用的字符串集合。“系統化的”描述方式就是一種 描述串檢索模式的語言（簡單串匹配的“模式語言”就是字符串本 身）如何（或，是否可能）高效實現所希望的檢查（匹配）

模式描述語言的功能很強，就可能描述更多更復雜的模式（對應的，字符串集合），但匹配算法的復雜性也會提高。這方面有許多理論結果?模式語言變得比較復雜以后，或許只能做出具有指數復雜性的匹配算法，這種情況使模式語言變得沒有實用意義?如果模式語言進一步復雜，模式匹配問題甚至可能變為不可計算問題。也就是說，根本不可能寫出完成匹配的算法。這樣的描述語言就完全沒有實際價值了?有意義的模式描述語言是描述能力和處理效率之間的合理平衡模式匹配的進一步問題

如果大家對DOS操作系統或者Windows命令窗口（cmd）有些了解，可能會知道描述文件名的“通配符”?在Windows系統里搜索文件，也會用到?Windows/DOS的文件名描述中可以使用兩個通配符*和?寫在文件名字符串里的?可以與任何實際字符匹配*可與任意一串字符匹配?例：*.py與所有以py為擴展名的文件名匹配在普通字符串的基礎上增加通配符，形成了一種功能更強的模式語言?一個模式描述一集字符串，例如a?b描述所有3個字符的串，其首字符為a，尾字符為b，中間字符任意?能描述無窮字符串集合，例如a*描述了所有以a開頭的字符串但，只是加入了通配符的模式語言還不夠靈活（描述能力不夠強）數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/正則表達式數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

一種很有意義的實用模式語言是正則表達式（RegularExpression,或稱regex、regexp、RE、re），由邏輯學家Kleene提出一個具體的正則表達式，描述字符集上的一個字符串集合

正則表達式語言的基本成分是字符集里的普通字符，另外還有幾種特殊的組合結構（以及表示組合的括號）?正則表達式里的普通字符只與該字符本身匹配?順序組合?

選擇組合

|：若

匹配

s，：若

匹配

s，匹配

t，那么

匹配

t，

|匹配st匹配s也匹配t?

星號

*：與

0

段或者任意多段與

匹配的序列的拼接串匹配例：?abc只與串abc匹配?a(b*)(c*)與所有一個a之后任意個b再后任意個c的串匹配?a((b|c)*)與所有一個a后任意個b和c組成的序列匹配正則表達式數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/這里不需要通配符?通配符?可以用|描述（由于字符集是有窮集）?通配符*可以通過|和星號描述正則表達式在實際的信息處理中非常有用?人們以各種形式將其納入編程語言或者語言的標準庫?存在很多不同設計，它們都是理論的正則表達式的子集或變形，基于對易用性和實現效率等方面的考慮，還可能有些擴充?許多腳本語言提供正則表達式功能，一些常規語言正在或計劃把正則表達式納入標準庫，C/C++/Java等語言也有正則表達式包?經過在Perl語言里的精煉，基本形成了一套比較標準的形式

可以看到許多有關正則表達式的書籍或文章，把正則表達式說成是程序員必備的重要武器，等等。網上的討論很熱鬧，有若干書籍正則表達式數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/有關書籍Python正則表達式

Python的正則表達式功能由標準包re提供。正則表達式可以幫助我們實現一些復雜的字符串操作。正確使用這個包?需要理解正則表達式的描述規則和效用?理解使用正則表達式的各種方法正則表達式采用Python字符串的形式描述（引號括起的字符序列）?在用于一些特殊的操作時，一個具有正則表達式形式的字符串代表一種字符串模式，它能與特定的一集字符串匹配?正則表達式的描述形式實際上構成一種特殊的“小語言”語法：re規定的特殊描述規則語義：一個正則表達式所描述的那一集字符串

Python文檔HOWTO里有一節Regular

Expression

HOWTO。網上有些介紹Python正則表達式的網頁，一些Python書籍里有討論數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/原始字符串數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/在介紹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語言版）：字符串裘宗燕，5/3/2020-/1/

Python正則表達式包re規定了一組特殊字符，稱為“元字符”。它們在匹配字符串時起著特殊的作用。這種字符一共14個.

^

$

*

+

?

\

|

{

}

[

]

(

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

表示被處理的字符串，repl

表示替換串正則表達式數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/生成正則表達式對象：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對象里記錄成功匹配的相關信息，可以根據需要取出和使用。也可以簡單地把它作為一個真值用于邏輯判斷正則表達式數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/匹配：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("

",

"abc

abb

are

not

the

same")得到：

["abc",

"abb",

"are",

"not",

"the",

"same"]re.split("

",

"1

2

3

4")

#

分割出了幾個空串得到：["1","2","","3","","","4"]正則表達式數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/找到所有匹配串：re.findall(pattern,string,flags=0)本函數返回一個表，其元素按順序給出string里與pattern匹配的（從左到右非重疊的）各個子串如果模式里只有常規字符，做這種匹配的價值不大，因為結果表里所有的字符串相同。但用一般的正則表達式模式，情況就會不同還有操作后面介紹，下面逐步介紹正則表達式的情況。正則表達式的描述數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

如前所說，Python標準庫包re的正則表達式就是一類特殊形式的字符串，可用于re里定義的一些函數，完成一些字符串操作正則表達式的最基本組合是順序組合

，若匹配

s，

匹配

t，那匹配s+t（s,t為字符串，Python寫法s+t是兩個字符串的拼接）注意，在正則表達式里，同樣可以（也常常需要）寫普通Python字符串使用的換意字符，如\n表示換行，\t表示制表符等正則表達式里的空格也是常規字符，它只與自己匹配下面分門別類介紹一些特殊的描述形式，需要注意兩點：?

一種表達式（或元符號）的構造形式（描述形式）?

這種表達式能匹配怎樣的字符串（集合）字符組數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/字符組表達式[...]匹配括號中列出的任一個字符

[abc]可以匹配字符a或b或c區間形式[0-9]是順序列出的縮寫，匹配所有十進制數字字符[0-9a-zA-Z]匹配所有字母（英文字母）和數字[^...]中的^表示求補，這種模式匹配所有未在括號里列出的字符

[^0-9]匹配所有非十進制數字的字符[^\t\v\n\f\r]匹配所有非空白字符（非空格/制表符/換行符）如果需要在字符組里包括^，就不能放在第一個位置，或者寫\^；如果需要在字符組包括-]，也必須寫\-或\]圓點字符.匹配任意一個字符.b匹配所有以a開頭b結束的四字符串

a[1-9][0-9]匹配a10,a11,...,a99常用字符組數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/為了方便，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("[,]*","1

2,3

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

"abbaaabbdbbabbababbabb")得到["","bb","bbdbb","bb","b","bb","bb"]

注意，re.match("ab*","abbbbbbc")時，模式可以與a匹配，與ab匹配，等等，它究竟匹配那個串？兩種可能?貪婪匹配：與有可能匹配的最長子串匹配在這里ab*匹配abbbbbb，*運算符做貪婪匹配?非貪婪匹配：與有可能匹配的最短子串匹配數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/重復數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/與*略微不同的重復運算符+表示1次或多次重復例：描述正整數的一種簡單模式"\d+"，等價于"\d\d*"可選（片段）用?運算符表示?表示0次或1次重復例，描述整數（表示整數的字符串）的一種簡單模式"-?\d+"確定次數的重復用

{n}

表示，

{n}

與

匹配的串的n次重復匹配 描述北京常規的固話號碼："(010-)?[2-9][0-9]{7}"注意：這種表達式描述的通常是實際字符串集合的超集，但可以用注意：上面描述中出現了圓括號，描述?的作用范圍?*,?,{3}有作用范圍問題（優先級），它們作用于最小表達式?"010-?"表示其中的"–"可選，"(010-)?"表示整個段可選重復數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/重復范圍用

{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}?（各運算符后增加一個問號）的語義與上面幾個運算符分別對應，但采用非貪婪匹配（最小匹配）的策略選擇數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

選擇運算符

|

描述兩種或多種情況之一的匹配。如果

或者

與一個串匹配，那么

|

就與之匹配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}首尾匹配數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/行首匹配：以^符號開頭的模式，只能與一行的前綴子串匹配

re.search("^for","books

for

children")得到None行尾匹配：以$符號結尾的模式，只與一行的后綴匹配

re.search("fish$","cats

like

to

eat

fishes")得到None注意，“一行的”前綴/后綴包括整個被匹配串的前綴和后綴。如串里有換行符，還包括換行符前的子串（一行的后綴）和其后的子串（前綴）串首匹配：\A開頭的模式只與被匹配串的前綴匹配串尾匹配：\Z結束的模式只與被匹配串的后綴匹配至此我們已經介紹了所有14個元字符應特別提出換意字符\，以它作為引導符定義了一批換意元字符，如\d,\D等。它還用于在模式串里寫非打印字符（如\t,\n,...）和\\等，在[]里寫\^,\-,\]單詞邊界數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/兩個換意元字符用于描述特殊子串的邊界

\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"單詞邊界數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/實例：一般的可能帶正負號的整數，可以考慮用模式"[+-]?\\b(0+|[1-9]\d*)\\b"但它匹配x+5里的+5，但不匹配3+-5里的-5。寫這種表達式和使用時，都需要考慮被匹配對象的情況例：求一個Python程序里出現的所有整數之和

def

sumInt(fname):re_int

=

"\\b(0+|[1-9]\d*)\\b"inf

=

open(fname)if

inf

==

None:return

0ilist=map(int,re.findall(re_int,inf.read()))#可改為分行s=0for

n

in

ilist:s

+=

nreturn

s邊界數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/\B是\b的補，也是匹配空串，但要求相應位置是字母或數字實例：>>>

re.findall("py.\B",

"python,

py2,

py342,

py1py2py4")["pyt","py3",

"py1","py2"]匹配對象（match對象）數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/

許多匹配函數在匹配成功時返回一個match對象，對象里記錄了所完成匹配的有關信息，可以取出使用。下面介紹這方面的情況

首先，這樣的匹配結果可以用于邏輯判斷，成功時得到的match對象總表示邏輯真，不成功得到的None表示假。例如match1

=

re.search(

pt,

text)if

match1:...match1...text...#使用match對象的處理操作

match對象提供了一組方法，用于檢查與匹配有關的信息。下面介紹一些基本用法，更多信息（包括可選參數）見re包文檔在下面介紹中，mat

表示通過匹配得到的一個match對象取得被匹配的子串：mat.group()在一次成功匹配中，所用的正則表達式匹配了目標串的一個子串，操作

mat.group()給出這個子串匹配對象（match對象）數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/在目標串里的匹配位置：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）數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/正則表達式描述中的另一個重要概念是組（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表示一個整數序號模式里的組數據結構和算法（Python語言版）：字符串裘宗燕，5/3/2020-/1/例：r"(.{2})\1"可匹配"ok

ok"或"no

no"，不匹配"no

oh"?注意，組編號應該是\1,\2等，但在普通字符串里，\1表示二進制編碼為1（經常可以看到被寫成0x01）的那個（特殊）字符，而現在需要模式串里出現\1,\2等?為此上面模式需要寫成"(.{2})

\\1"，或者用原始字符串形式簡化寫法，寫為

r"(.