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

1、數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/1/3 3，字符串，字符串v 字符串的相關概念字符串的相關概念v Python 字符串（回顧）字符串（回顧）v 字符串匹配和算法字符串匹配和算法v 進一步的模式匹配問題進一步的模式匹配問題v 正則表達式正則表達式v Python 的正則表達式的正則表達式v 應用舉例應用舉例數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/2/字符串字符串n討論字符串，首先要有一個確定的討論字符串，首先要有一個確定的字符集字符集q“字符字符”是一個抽象概念，字符集是有窮的一組字符構成的集合是一個抽象概念，字符集

2、是有窮的一組字符構成的集合q人們經?？紤]在計算機里使用的標準字符集，實際上，完全可以拿人們經?？紤]在計算機里使用的標準字符集，實際上，完全可以拿任意數(shù)據(jù)元素的集合作為字符集任意數(shù)據(jù)元素的集合作為字符集n字符串字符串（簡稱（簡稱串串）是特殊的線性表，表中元素取自選定的字符集）是特殊的線性表，表中元素取自選定的字符集其不同于一般表的特點是支持其不同于一般表的特點是支持一組以串為對象的操作一組以串為對象的操作n長度長度：串中字符的個數(shù)稱為串的：串中字符的個數(shù)稱為串的長度長度q長度為長度為 0 的串稱為的串稱為空串空串q在任意一個字符集里，只有唯一的一個空串在任意一個字符集里，只有唯一的一個空串n與一

3、般的表類似：與一般的表類似：q字符串里的字符順序排列，串里的每個字符有其確定位置字符串里的字符順序排列，串里的每個字符有其確定位置q我們用我們用 0 開始的自然數(shù)表示位置開始的自然數(shù)表示位置數(shù)據(jù)結構和算法（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數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/4/字符串字符串n兩個串之間還有一個重要的關系是兩個串之間還有一個重要的關系是“子串關系子串關系”n稱稱 s1 為為 s2 的一個的一個子串子串，如果存在兩個串，如果存在兩個串 s 和和 s 使下式成立使下式成立s2 = s + s1 + s （借用借用 Python 的寫法）的寫法）q子串也是串。直觀看，子串是原串中連續(xù)的一段字符序列形成的串。子串也是串。直觀看，子串是原串中連續(xù)的一段字符序列形成的串。顯然，一個串可以是或者不是另一個串的子串顯然，一個串可以是或者不是另一個串的子串q如果如果 s1 是是 s2

6、 的子串，也說的子串，也說 s1 在在 s2 里里出現(xiàn)出現(xiàn)，稱，稱 s2 里與里與 s1 相同的相同的字符段的第一個字符的位置為字符段的第一個字符的位置為 s1 在在 s2 里里出現(xiàn)的位置出現(xiàn)的位置qs2 里可能出現(xiàn)多個與里可能出現(xiàn)多個與 s1 相同的段，這時說相同的段，這時說 s1 在在 s2 里多次出現(xiàn)里多次出現(xiàn)n注意：注意：s1 在在 s2 中的多個出現(xiàn)可能不獨立，相互重疊。例如中的多個出現(xiàn)可能不獨立，相互重疊。例如babb 在在 babbabbbbabb 里有三個出現(xiàn)，前兩個有重疊里有三個出現(xiàn)，前兩個有重疊n根據(jù)定義，很顯然，空串是任何字符串的子串；另一方面，任何字符串根據(jù)定義，很顯然

7、，空串是任何字符串的子串；另一方面，任何字符串 s 也都是該串本身的子串也都是該串本身的子串數(shù)據(jù)結構和算法（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 是連續(xù)是連續(xù) n 個個 s 拼接而成的串（在拼接而成的串（在 Python 語言里語言里用用 s * n 表示）表示）q串替換，指將一個串里的一些（互不重疊的）子串代換為另一些串串替換，指將一個串里的一些（互不重疊的）子串代換為另一些串得到的結果（由于可能重疊，需規(guī)定代換的順序，如從左到右）得到的結果（由于可能重疊，需規(guī)定代換的順序，如從左到右）q還有許多有用的串運算，可以參考還有許多有用的串運算，可以參考 Python 的的 str 類型

9、，或其他語類型，或其他語言的字符串類型（經典是言的字符串類型（經典是 SNOBOL 語言）語言）數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/6/字符串的理論字符串的理論n字符串集合和拼接操作構成了一種代數(shù)結構字符串集合和拼接操作構成了一種代數(shù)結構q空串是拼接操作的空串是拼接操作的“單位元單位元” （幺元）（幺元） 有結合律，無交換律有結合律，無交換律q串集合加上拼接操作，構成一個半群串集合加上拼接操作，構成一個半群一種典型的非交換半群一種典型的非交換半群q有單位元，因此是一個幺半群有單位元，因此是一個幺半群n關于串的理論有許多研究工作關于串的理論有許多研究工作q

10、基于串和串替換，研究者提出了基于串和串替換，研究者提出了 post 系統(tǒng)系統(tǒng)這是一種與圖靈機等價的計算模型這是一種與圖靈機等價的計算模型q（串）重寫系統(tǒng)（串）重寫系統(tǒng)（rewriting system）是計算機理論的一個研究領是計算機理論的一個研究領域，一直非?；钴S，有許多重要結果和應用域，一直非常活躍，有許多重要結果和應用數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/7/字符串抽象數(shù)據(jù)類型字符串抽象數(shù)據(jù)類型可以考慮下面的字符串抽象數(shù)據(jù)類型：可以考慮下面的字符串抽象數(shù)據(jù)類型：ADT String:String(self, sseq) # 基于字符序列基于字符序列s

11、seq建立一個字符串建立一個字符串is_empty(self) # 判斷本字符串是否空串判斷本字符串是否空串len(self) # 取得字符串的長度取得字符串的長度char(self, index) # 取得字符串中位置取得字符串中位置index的字符的字符substr(self, a, b) # 取得字符串中取得字符串中 a:b 的子串，左閉右開區(qū)間的子串，左閉右開區(qū)間match(self, string) # 查找串查找串string在本字符串中第一個出現(xiàn)的位置在本字符串中第一個出現(xiàn)的位置concat(self, string) # 做出本字符串與另一字符串做出本字符串與另一字符串stri

12、ng的拼接串的拼接串subst(self, str1, str2) # 做出將本字符串里的子串做出將本字符串里的子串str1 # 都替換為都替換為str2的結果串的結果串最后兩個操作可以實現(xiàn)為變動操作或非變動操作（生成滿足需要的新串）最后兩個操作可以實現(xiàn)為變動操作或非變動操作（生成滿足需要的新串）這里的大部分操作都很簡單，只有這里的大部分操作都很簡單，只有match和和subst操作比較復雜。易見，操作比較復雜。易見，subst 的基礎也是的基礎也是 match，因為要找，因為要找 str1 在串里的出現(xiàn)在串里的出現(xiàn)子串檢索（子串匹配）是字符串的核心操作，后面將詳細研究子串檢索（子串匹配）是字

13、符串的核心操作，后面將詳細研究數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/8/字符串的實現(xiàn)字符串的實現(xiàn)n串是字符的線性序列：串是字符的線性序列：q可采用線性表的實現(xiàn)方式，用順序表示和鏈接表示。例如用能動態(tài)可采用線性表的實現(xiàn)方式，用順序表示和鏈接表示。例如用能動態(tài)變化大小的順序表作為實現(xiàn)方式（如果需要表示可變的字符串）變化大小的順序表作為實現(xiàn)方式（如果需要表示可變的字符串）q還可以根據(jù)串本身的特點和串操作的特點，考慮其他表示方式。當還可以根據(jù)串本身的特點和串操作的特點，考慮其他表示方式。當然，無論如何還是基于然，無論如何還是基于順序存儲順序存儲或或/和和鏈接鏈接q

14、關鍵問題：表示方式應能很好支持串的管理和相關操作的實現(xiàn)關鍵問題：表示方式應能很好支持串的管理和相關操作的實現(xiàn)n字符串表示的兩個問題：字符串表示的兩個問題：q串內容存儲。兩個極端：串內容存儲。兩個極端：1，連續(xù)存儲在一塊存儲區(qū)；，連續(xù)存儲在一塊存儲區(qū)；2，一個字符，一個字符存入一個獨立存儲塊，鏈接起來。也可以采用某種中間方式，把串存入一個獨立存儲塊，鏈接起來。也可以采用某種中間方式，把串中字符分段保存在一組存儲塊里，鏈接起這些存儲塊中字符分段保存在一組存儲塊里，鏈接起這些存儲塊q串結束的表示，不同字符串長度可能不同，必須表示串到哪里結束。串結束的表示，不同字符串長度可能不同，必須表示串到哪里結束

15、。兩種基本方式：兩種基本方式：1，用專門數(shù)據(jù)域記錄字符串長度；，用專門數(shù)據(jù)域記錄字符串長度；2，用一個特殊，用一個特殊符號表示串結束（例如符號表示串結束（例如 C 語言的字符串采用這種方式）語言的字符串采用這種方式）數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/9/字符串的實現(xiàn)字符串的實現(xiàn)n現(xiàn)在考慮字符串的操作現(xiàn)在考慮字符串的操作許多串操作是線性表操作的具體實例，包括串拼接許多串操作是線性表操作的具體實例，包括串拼接下面考慮一個特殊的操作下面考慮一個特殊的操作n串替換串替換q牽涉到三個串：被處理的主串牽涉到三個串：被處理的主串 s，作為被替換對象需要從作為被替換對

16、象需要從 s 中替換中替換掉的子串掉的子串 t，以及用于代換以及用于代換 t 的的 tq由于由于 t 可能在可能在 s 中出現(xiàn)多次，因此需要通過一系列具體的子串代換中出現(xiàn)多次，因此需要通過一系列具體的子串代換完成整個替換完成整個替換q由于多次出現(xiàn)可能重疊（回憶前面的例子），只能規(guī)定一種代換順由于多次出現(xiàn)可能重疊（回憶前面的例子），只能規(guī)定一種代換順序（例如從左到右），一次代換破壞的子串不應再代入新串序（例如從左到右），一次代換破壞的子串不應再代入新串q一次子串代換后，應該從代入的新串之后繼續(xù)工作。即使代入新串一次子串代換后，應該從代入的新串之后繼續(xù)工作。即使代入新串之后形成的部分能與之后形成的

17、部分能與 t 匹配，也不應在本次替換中考慮匹配，也不應在本次替換中考慮q很容易看到：串替換的關鍵是找到匹配很容易看到：串替換的關鍵是找到匹配數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/10/實際語言里的字符串實際語言里的字符串n許多語言提供了標準的字符串功能，如許多語言提供了標準的字符串功能，如qC語言標準庫有一組字符串函數(shù)（語言標準庫有一組字符串函數(shù)（string.h），），一些一些C語言系統(tǒng)提供語言系統(tǒng)提供的擴展的字符串庫；的擴展的字符串庫；C+ 語言標準庫里的字符串庫語言標準庫里的字符串庫 qJava 標準庫的字符串庫標準庫的字符串庫q許多腳本語言（包括許

18、多腳本語言（包括 Python）提供了功能豐富的字符串庫提供了功能豐富的字符串庫n許多實際字符串庫用動態(tài)順序表結構作為字符串的表示方式許多實際字符串庫用動態(tài)順序表結構作為字符串的表示方式q這樣既能支持任意長的字符串這樣既能支持任意長的字符串q又能比較有效地實現(xiàn)各種重要的字符串操作又能比較有效地實現(xiàn)各種重要的字符串操作n實際上，支持不同的字符串操作，可能需要不同的實現(xiàn)，例如實際上，支持不同的字符串操作，可能需要不同的實現(xiàn)，例如q有些計算工作需要記錄和處理極長的字符串，如支持操作有些計算工作需要記錄和處理極長的字符串，如支持操作 MB（大大約為約為 106）或更長的字符串，采用連續(xù)存儲可能帶來管理

19、問題）或更長的字符串，采用連續(xù)存儲可能帶來管理問題q被編輯文本也是字符串，實現(xiàn)編輯器操作要考慮專門的字符串表示被編輯文本也是字符串，實現(xiàn)編輯器操作要考慮專門的字符串表示數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/11/Python 字符串字符串nPython 內部類型內部類型 str 是抽象字符串概念的一個實現(xiàn)是抽象字符串概念的一個實現(xiàn)qstr 是不變類型，是不變類型，str 對象創(chuàng)建后的內容（和長度）不變對象創(chuàng)建后的內容（和長度）不變q但不同的但不同的 str 對象長度不同，需要記錄對象長度不同，需要記錄nPython 采用一體式的連續(xù)形式表示采用一體式的連續(xù)

20、形式表示 str 對象，見下圖對象，見下圖其他其他長度長度len串內容存儲區(qū)串內容存儲區(qū).nstr 對象的操作分為兩類：對象的操作分為兩類：q獲取獲取 str 對象的信息，如得到串長，檢查串內容是否全為數(shù)字等對象的信息，如得到串長，檢查串內容是否全為數(shù)字等q基于基于 str 對象構造新的對象構造新的 str 對象，包括切片，構造小寫對象，包括切片，構造小寫/大寫拷貝，大寫拷貝，各種格式化等。切分是構造包含多個字符串的表各種格式化等。切分是構造包含多個字符串的表n一些操作屬子串匹配，如一些操作屬子串匹配，如 count 檢查子串出現(xiàn)次數(shù)，檢查子串出現(xiàn)次數(shù)，endwith 檢查后檢查后綴，綴，fi

21、nd/index 找子串位置等。這類操作最重要，后面專門討論找子串位置等。這類操作最重要，后面專門討論數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/12/字符串操作的實現(xiàn)字符串操作的實現(xiàn)n檢查字符串內容的操作可以分為兩類檢查字符串內容的操作可以分為兩類qO(1) 時間的簡單操作，包括時間的簡單操作，包括 len 和定位訪問（也構造新字符串）和定位訪問（也構造新字符串）q其他都需要掃描整個串的內容，包括不變序列的共有操作（其他都需要掃描整個串的內容，包括不變序列的共有操作（in、not in、min/max），各種字符類型判斷（如是否全為數(shù)字），各種字符類型判斷（如

22、是否全為數(shù)字）o 需通過一個循環(huán)逐個檢查串中字符完成工作，需通過一個循環(huán)逐個檢查串中字符完成工作，O(n) 操作操作o 子串查找和匹配的問題后面討論子串查找和匹配的問題后面討論n需要構造新字符串的操作情況比較復雜，基本模式都包括兩部分工作需要構造新字符串的操作情況比較復雜，基本模式都包括兩部分工作1, 為新構造的串安排一塊存儲為新構造的串安排一塊存儲2, 根據(jù)被操作串（和可能的參數(shù)串）構造出一個新串根據(jù)被操作串（和可能的參數(shù)串）構造出一個新串n以以 sa:b:k 為例，算法：為例，算法：1, 根據(jù)根據(jù) a、b、k 算出新字符串的長度算出新字符串的長度2, for i in range(a, b

23、, k) : 拷貝拷貝 si 到新串里的下一個空位到新串里的下一個空位數(shù)據(jù)結構和算法（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 也可以有一定規(guī)模，也可能需要也可以有一定規(guī)模，也可能需要做許多模式串和做許多模式串和/或許多目標串的匹配，有關算法的效率非常重要或許多目標串的匹配，有關算法的效率非常重要數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/14/串匹配串匹配n許多計算機應用的最基本操作是字符串匹配。如許多計算機應用的最基本操作是字符串匹配。如q用編輯器或字處理系統(tǒng)工作時，在文本中查找單詞或句子（中文字用編輯器或字處理系統(tǒng)工作時，在文本中查找單詞或句子（中文字或詞語），在程序里找拼寫錯誤的標識符等或詞語），在程序里找拼寫錯誤的標識符等qemail 程序的垃圾郵件過濾器，程序的垃圾

26、郵件過濾器，google 等網絡檢索系統(tǒng)等網絡檢索系統(tǒng)q各種防病毒軟件，主要靠在文件里檢索病毒模式串各種防病毒軟件，主要靠在文件里檢索病毒模式串n在分子生物學領域：在分子生物學領域：DNA 細胞核里的一類長分子，在遺傳中起著核心細胞核里的一類長分子，在遺傳中起著核心作用。作用。DNA 內有四種堿基：腺嘌吟內有四種堿基：腺嘌吟(adenine)，胞嘧啶胞嘧啶(cytosine)，鳥鳥嘌吟嘌吟(guanine)，胸腺嘧啶胸腺嘧啶(thymine)。它們的不同組合形成氨基酸、蛋它們的不同組合形成氨基酸、蛋白質和其他更高級的生命結構白質和其他更高級的生命結構qDNA 片段可看作是片段可看作是a,c,g

27、,t構成的模式，如構成的模式，如 acgatactagacagtq考查在蛋白質中是否出現(xiàn)某個考查在蛋白質中是否出現(xiàn)某個 DNA 片段，可看成與該片段，可看成與該 DNA 片段片段的串匹配問題。的串匹配問題。DNA 分子可以切斷和拼接，切斷動作由各種酶完分子可以切斷和拼接，切斷動作由各種酶完成，酶也是采用特定的模式確定剪切位置成，酶也是采用特定的模式確定剪切位置數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/15/串匹配串匹配n實際中模式匹配的規(guī)模（實際中模式匹配的規(guī)模（n 和和 m）可能非常大，而且有時間要求可能非常大，而且有時間要求q被檢索的文本可能很大被檢索的文

28、本可能很大q網絡搜索需要處理億萬的網頁網絡搜索需要處理億萬的網頁q防病毒軟件要在合理時間內檢查數(shù)以十萬計的文件（以防病毒軟件要在合理時間內檢查數(shù)以十萬計的文件（以 GB 計）計）q運行在服務器上的郵件過濾程序，可能需要在一秒鐘的時間內掃描運行在服務器上的郵件過濾程序，可能需要在一秒鐘的時間內掃描數(shù)以萬計的郵件和附件數(shù)以萬計的郵件和附件q為疾病為疾病/藥物研究藥物研究/新作物培養(yǎng)等生物學工程應用，需要用大量新作物培養(yǎng)等生物學工程應用，需要用大量 DNA模式與大量模式與大量 DNA 樣本（都是樣本（都是 DNA 序列）匹配序列）匹配n由于在計算機科學、生物信息學等許多領域的重要應用，串模式匹配問由

29、于在計算機科學、生物信息學等許多領域的重要應用，串模式匹配問題已成為一個極端重要的計算問題。高效的串匹配算法非常重要題已成為一個極端重要的計算問題。高效的串匹配算法非常重要q有幾個集中關注字符串匹配問題的國際學術會議，曾經有過專門的有幾個集中關注字符串匹配問題的國際學術會議，曾經有過專門的國際競賽（見國際競賽（見 wiki 頁和萬維網）頁和萬維網）q目前全世界一大半的計算能力是在做串模式匹配（做目前全世界一大半的計算能力是在做串模式匹配（做 DNA 分析）分析）數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/16/串匹配和算法串匹配和算法n還需注意不同的實際需要，如

30、還需注意不同的實際需要，如q用一個模式在很長的目標串里反復匹配（確定出現(xiàn)位置）用一個模式在很長的目標串里反復匹配（確定出現(xiàn)位置）q一組（可能很多）模式，在一個或一組目標串里確定是否有匹配一組（可能很多）模式，在一個或一組目標串里確定是否有匹配n不同算法在處理不同實際情況時可能有不同的表現(xiàn)不同算法在處理不同實際情況時可能有不同的表現(xiàn)人們已經開發(fā)出一批有意義的（有趣）算法（進一步情況見人們已經開發(fā)出一批有意義的（有趣）算法（進一步情況見 wiki）n粗看，字符串匹配是一個很簡單的問題粗看，字符串匹配是一個很簡單的問題q字符串是簡單數(shù)據(jù)（字符）的簡單序列，結構也最簡單（順序）字符串是簡單數(shù)據(jù)（字符）

31、的簡單序列，結構也最簡單（順序）q很容易想到最簡單而直接的算法很容易想到最簡單而直接的算法q但事實是：直接而簡單的算法并不是高效的算法但事實是：直接而簡單的算法并不是高效的算法因為它可能沒有很好利用問題的內在結構因為它可能沒有很好利用問題的內在結構q字符串匹配貌似簡單，但人們已開發(fā)出許多字符串匹配貌似簡單，但人們已開發(fā)出許多“大相徑庭的大相徑庭的”算法算法數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/17/串匹配的樸素算法串匹配的樸素算法n串匹配的基礎是逐個比較字符串匹配的基礎是逐個比較字符q如果從目標串的某個位置開始，模式串的每個字符都與目標串里的如果從目標串的

32、某個位置開始，模式串的每個字符都與目標串里的對應字符相同，這就是一個匹配對應字符相同，這就是一個匹配q如果出現(xiàn)一對不同字符，就是不匹配如果出現(xiàn)一對不同字符，就是不匹配n算法設計的關鍵：算法設計的關鍵：1，怎樣比較字符；，怎樣比較字符；2，發(fā)現(xiàn)不匹配后下一步怎么做，發(fā)現(xiàn)不匹配后下一步怎么做q對上述兩點采用不同的策略，就形成了不同的算法對上述兩點采用不同的策略，就形成了不同的算法q從下面兩個例子可以看到一些情況，更多實例見從下面兩個例子可以看到一些情況，更多實例見 wikin樸素匹配算法：樸素匹配算法：1，從左到右匹配；，從左到右匹配；2，發(fā)現(xiàn)不匹配時，考慮目標串里的，發(fā)現(xiàn)不匹配時，考慮目標串里的

33、下一位置是否存在匹配下一位置是否存在匹配 t a b b b a a p a b a a b a a b a a b a 數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/18/串匹配的樸素算法串匹配的樸素算法n樸素的串匹配算法的一個實現(xiàn)：樸素的串匹配算法的一個實現(xià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樸素匹配算法簡單，易理解，但效率低樸素匹配算法簡單，易理解，但效率低造成效率的主要操作是執(zhí)行中可能出現(xiàn)的回溯：遇字符不等時將模式造成效率的主要操作是執(zhí)行中可能出現(xiàn)的回溯：遇字符不等時將模式串串 p 右移一個字符，再次從右移一個字符，再次從 p0（重置重置 j = 0 后）開始比較后）開始比較數(shù)據(jù)結構和算法（Pytho

35、n 語言版）：字符串裘宗燕，2021-9-20-/19/串匹配的樸素算法串匹配的樸素算法n最壞情況是每趟比較都在最后出現(xiàn)不等，最多比較最壞情況是每趟比較都在最后出現(xiàn)不等，最多比較 nm1 趟，總比趟，總比較次數(shù)為較次數(shù)為 m*(nm1)，所以算法時間復雜性為所以算法時間復雜性為 O(m*n)n最壞情況的一個實例最壞情況的一個實例目標串：目標串：00000000000000000000000000000000000000001模式串：模式串：00000001n樸素算法效率低的原因：把每次字符比較看作完全獨立的操作樸素算法效率低的原因：把每次字符比較看作完全獨立的操作q完全沒有利用字符串本身的特點

36、（每個字符串都是特殊的）完全沒有利用字符串本身的特點（每個字符串都是特殊的）q沒有利用前面已做過的字符比較得到的信息沒有利用前面已做過的字符比較得到的信息n從數(shù)學上看，這樣做相當于認為目標串和模式串里的字符都是隨機量，從數(shù)學上看，這樣做相當于認為目標串和模式串里的字符都是隨機量，而且有無窮多可能取值，兩次字符比較相互無關也不可借鑒而且有無窮多可能取值，兩次字符比較相互無關也不可借鑒q實際字符串取值來自一個有窮集合實際字符串取值來自一個有窮集合q每個串都有窮。特別是模式串通常不太長，而且可能反復使用每個串都有窮。特別是模式串通常不太長，而且可能反復使用數(shù)據(jù)結構和算法（Python 語言版）：字符

37、串裘宗燕，2021-9-20-/20/無回溯匹配：無回溯匹配：KMP算法算法nKMP 算法是一個高效串匹配算法。由算法是一個高效串匹配算法。由 D. E. Knuth 和和 V. R. Pratt 提出，提出，J. H. Morris 幾乎同時發(fā)現(xiàn)，因此稱幾乎同時發(fā)現(xiàn)，因此稱 KMP 算法。這是本課程中第一個算法。這是本課程中第一個非平凡算法，基于對問題的深入分析，算法不易理解但效率高非平凡算法，基于對問題的深入分析，算法不易理解但效率高n要理解要理解 KMP 算法，首先需要了解樸素算法的缺陷?，F(xiàn)在仔細考察樸素算法，首先需要了解樸素算法的缺陷?，F(xiàn)在仔細考察樸素算法的執(zhí)行過程。設目標串算法的執(zhí)行

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模式串為匹配前模式串為匹配前已知，在匹配中已知，在匹配中反復使用反復使用若先對模式串做若先對模式串做細致分析，記錄細致分析，記錄有用信息（有用信息（ 靜態(tài)靜態(tài)預處理），有可預處理），有可能加快匹配能加快匹配數(shù)據(jù)結構和算法（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 失?。ㄔO遇到失?。ㄔO遇到 pi tj），），就去找到就去找到某個某個 pki，0 ki i，下一步用下一步用 pki 去與去與 tj 比較比較n要正確前移，對模式要正確前移，對模式 p 的每個的每個 pi，都應能找到相應的都應能找到相應的 pki。問題是，無問題是，

41、無論對怎樣的論對怎樣的 tj 失敗，對相應的失敗，對相應的 i，對應對應 ki 都一樣嗎？都一樣嗎？數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/22/無回溯匹配：分析無回溯匹配：分析n關鍵認識：在關鍵認識：在 pi 匹配失敗時，所有匹配失敗時，所有 pk（0 k i）都已匹配成功（否則都已匹配成功（否則不會考慮不會考慮 pi 的匹配）。也就是說：的匹配）。也就是說：tj 之前的之前的 i-1 個字符就是個字符就是 p 的前的前 i-1 個字符個字符?。海。涸緫摳鶕?jù)原本應該根據(jù) t 的情況確定前移方式，但實際上可以根據(jù)的情況確定前移方式，但實際上可以根據(jù) 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 匹配失敗時，有可能發(fā)現(xiàn)用匹配失敗時，有可能發(fā)現(xiàn)用 pi 之前的所有之前的所有 p 字符與字符與 t 字符的比較都沒有利用價值，下一步應該從頭開始，用字符的比較都沒有利用價值，下一步應該從頭開始，用 p0 與與 tj+1 比較。比較。遇到這種特殊情況就在遇到這種特殊情況就在 pnexti 里記錄里記錄 1顯然，對任何模式都有：顯然，對任何模式都有：pnext 0 = -1數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/23/KMP算法算法n假設已經根據(jù)模式串假設已經

44、根據(jù)模式串 p 做出了做出了 pnext 表，考慮表，考慮 KMP 算法的實現(xiàn)算法的實現(xiàn)n匹配循環(huán)很容易寫出，如下：匹配循環(huá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數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/24/KMP算法算法n匹配函數(shù)的定義：匹配函數(shù)的定義：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算法復雜性的關鍵是循環(huán)。注意循環(huán)中算法復雜性的關鍵是循環(huán)。注意循環(huán)中 j 的值遞增，但加一的總次數(shù)不的值遞增，但加一的總次數(shù)不多于多于 n = len(t)。而且。而且 j 遞增時遞增時 i 值也遞增。另一方面值也

47、遞增。另一方面 i = pnexti 總使總使 i 值減小，但條件保證其值不小于值減小，但條件保證其值不小于 1，因此，因此 i = pnexti 的執(zhí)行次數(shù)不的執(zhí)行次數(shù)不會多于會多于 i 值遞增的次數(shù)。循環(huán)次數(shù)是值遞增的次數(shù)。循環(huán)次數(shù)是 O(n)，算法復雜性也是算法復雜性也是 O(n)數(shù)據(jù)結構和算法（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現(xiàn)在考慮現(xiàn)在考慮 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 個字符個字符數(shù)據(jù)結構和算法（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 匹配匹配數(shù)據(jù)結構和算法（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 值加一后繼續(xù)遞推（循環(huán)）值加一后繼續(xù)遞推（循環(huán)）q若若pk pi 設設 k 為為 pnextk 的值（

52、設的值（設 k 為為 pnextk，也就是去考慮也就是去考慮前一個更短的保證匹配的前綴，從那里繼續(xù)檢查）前一個更短的保證匹配的前綴，從那里繼續(xù)檢查）1.若若 k 值為值為 -1（一定來自（一定來自 pnext），得到，得到 p0 pi-kpi 中最大相同前中最大相同前后綴的長度為后綴的長度為 0，設設 pnext i+1 = 0，將將 i 值加一后繼續(xù)遞推值加一后繼續(xù)遞推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，繼續(xù)繼續(xù)q否則把否則把 p0.pk-1的最長相同前綴移過來繼續(xù)檢查的最長相同前綴移過來繼續(xù)檢查數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/28/KMP算法：生成算法：生成 pnext 表表n生成生成 pnext 表的表的 Python 函數(shù)定義函數(shù)定義def gen_pnext(p): i, k, m = 0, -1, len(p) pnext = -1 * m # 初始數(shù)組元素全為初始數(shù)組元素全為 -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 的生成算法還可以改進，下面討論的生成算法還可以改進，下面討論數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/29/生成生成 pnext 表：改進表：改進n設置設置 pnexti 時有一點情況可以考慮：時有一點情況可以

55、考慮：t0tj-i-1p0pj-1tj p0pi-1pi在在 pi tj 時（假設時（假設 pnexti = k），），如果發(fā)現(xiàn)如果發(fā)現(xiàn) pi = pk，那么一定那么一定 pk tj 。所以模式串應所以模式串應右右移到移到 pnextk，下一步用，下一步用 pnextk 與與 tj 比較比較n改造的算法只有循環(huán)體最后的語句不同：改造的算法只有循環(huá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數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/30/生成生成 pnext 表：復雜性表：復雜性n算法復雜性的主要因素是循環(huán)算法復雜性的主要因素是循環(huán)與與 KMP 主算法的分析類似：主算法的分析類似：qi 值遞增，但不超過值遞增，但不超過 p 的長度的長度 m，說明大循環(huán)體執(zhí)行說明大循環(huán)體執(zhí)行 m 次次qi 加一時加一時 k 也加一，說明也加一，說明 k 值加一值加一 m 次次q內層循環(huán)執(zhí)行總

57、導致內層循環(huán)執(zhí)行總導致 k 值減小，但不會小于值減小，但不會小于 1上面情況說明循環(huán)體的執(zhí)行次數(shù)為上面情況說明循環(huán)體的執(zhí)行次數(shù)為 O(m)，算法復雜性也是算法復雜性也是 O(m)nKMP 算法包括算法包括 pnext 表構造和實際匹配，表構造和實際匹配，O(m+n)。通常情況通常情況 m re.findall(py.B, python, py2, py342, py1py2py4)pyt, py3, py1, py2數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/56/匹配對象（匹配對象（match 對象）對象）n許多匹配函數(shù)在匹配成功時返回一個許多匹配函數(shù)在匹配成

58、功時返回一個 match 對象，對象里記錄了所完對象，對象里記錄了所完成匹配的有關信息，可以取出使用。下面介紹這方面的情況成匹配的有關信息，可以取出使用。下面介紹這方面的情況n首先，這樣的匹配結果可以用于邏輯判斷，成功時得到的首先，這樣的匹配結果可以用于邏輯判斷，成功時得到的 match 對象對象總表示邏輯真，不成功得到的總表示邏輯真，不成功得到的 None 表示假。例如表示假。例如match1 = re.search( pt, text)if match1: . match1 . text . # 使用使用 match 對象的處理操作對象的處理操作nmatch 對象提供了一組方法，用于檢查與

59、匹配有關的信息。下面介紹對象提供了一組方法，用于檢查與匹配有關的信息。下面介紹一些基本用法，更多信息（包括可選參數(shù)）見一些基本用法，更多信息（包括可選參數(shù)）見 re 包文檔包文檔在下面介紹中，在下面介紹中，mat 表示通過匹配得到的一個表示通過匹配得到的一個 match 對象對象n取得被匹配的子串：取得被匹配的子串：mat.group()在一次成功匹配中，所用的正則表達式匹配了目標串的一個子串，操在一次成功匹配中，所用的正則表達式匹配了目標串的一個子串，操作作 mat.group() 給出這個子串給出這個子串數(shù)據(jù)結構和算法（Python 語言版）：字符串裘宗燕，2021-9-20-/57/匹配

60、對象（匹配對象（match 對象）對象）n在目標串里的匹配位置：在目標串里的匹配位置：mat.start()得到得到 mat 代表的成功匹配在目標串里的實際匹配位置，這是目標串的代表的成功匹配在目標串里的實際匹配位置，這是目標串的一個字符位置（下標）一個字符位置（下標）n目標串里被匹配子串的結束位置：目標串里被匹配子串的結束位置：mat.end()這個位置采用常規(guī)表示方式。設這個位置采用常規(guī)表示方式。設 text 是目標串，有如下關系：是目標串，有如下關系：mat.group() = textmat.start():mat.end()n目標串里被匹配的區(qū)間：目標串里被匹配的區(qū)間：mat.spa