圖

如何存儲微博、微信等社交網絡中的好友關系？圖。實際上，涉及圖的算法有很多，也非常復雜，比如圖的搜索、最短路徑、最小生成樹、二分圖等等。我們今天聚焦在圖存儲這一方面，后面會分好幾節來依次講解圖相關的算法。

如何理解“圖”？

我們前面講過了樹這種非線性表數據結構，今天我們要講另一種非線性表數據結構，圖（Graph）。和樹比起來，這是一種更加復雜的非線性表結構。

圖中的元素我們就叫作頂點（vertex）。

圖中的一個頂點可以與任意其他頂點建立連接關系。我們把這種建立的關系叫作邊（edge）。

我們就拿微信舉例子吧。我們可以把每個用戶看作一個頂點。如果兩個用戶之間互加好友，那就在兩者之間建立一條邊。所以，整個微信的好友關系就可以用一張圖來表示。其中，每個用戶有多少個好友，對應到圖中，就叫作頂點的度（degree），就是跟頂點相連接的邊的條數。

微博的社交關系跟微信還有點不一樣，或者說更加復雜一點。微博允許單向關注，也就是說，用戶 A 關注了用戶 B，但用戶 B 可以不關注用戶 A。那我們如何用圖來表示這種單向的社交關系呢？（帶箭頭）

我們可以把剛剛講的圖結構稍微改造一下，引入邊的“方向”的概念。

如果用戶 A 關注了用戶 B，我們就在圖中畫一條從 A 到 B 的帶箭頭的邊，來表示邊的方向。如果用戶 A 和用戶 B 互相關注了，那我們就畫一條從 A 指向 B 的邊，再畫一條從 B 指向 A 的邊。我們把這種邊有方向的圖叫作“有向圖”。以此類推，我們把邊沒有方向的圖就叫作“無向圖”。

無向圖中有“度”這個概念，表示一個頂點有多少條邊。在有向圖中，我們把度分為入度（In-degree）和出度（Out-degree）。

頂點的入度，表示有多少條邊指向這個頂點；頂點的出度，表示有多少條邊是以這個頂點為起點指向其他頂點。對應到微博的例子，入度就表示有多少粉絲，出度就表示關注了多少人。

QQ 中的社交關系要更復雜的一點。不知道你有沒有留意過 QQ 親密度這樣一個功能。QQ 不僅記錄了用戶之間的好友關系，還記錄了兩個用戶之間的親密度，如果兩個用戶經常往來，那親密度就比較高；如果不經常往來，親密度就比較低。如何在圖中記錄這種好友關系的親密度呢？

這里就要用到另一種圖，帶權圖（weighted graph）。在帶權圖中，每條邊都有一個權重（weight），我們可以通過這個權重來表示 QQ 好友間的親密度。

如何在內存中存儲圖這種數據結構呢？

鄰接矩陣存儲方法：簡單，浪費內存空間

圖最直觀的一種存儲方法就是，鄰接矩陣（Adjacency Matrix）。

鄰接矩陣的底層依賴一個二維數組。對于無向圖來說，如果頂點 i 與頂點 j 之間有邊，我們就將 A[i][j] 和 A[j][i] 標記為 1；對于有向圖來說，如果頂點 i 到頂點 j 之間，有一條箭頭從頂點 i 指向頂點 j 的邊，那我們就將 A[i][j] 標記為 1。同理，如果有一條箭頭從頂點 j 指向頂點 i 的邊，我們就將 A[j][i] 標記為 1。對于帶權圖，數組中就存儲相應的權重。

如果我們存儲的是稀疏圖（Sparse Matrix），也就是說，頂點很多，但每個頂點的邊并不多，那鄰接矩陣的存儲方法就更加浪費空間了。比如微信有好幾億的用戶，對應到圖上就是好幾億的頂點。但是每個用戶的好友并不會很多，一般也就三五百個而已。如果我們用鄰接矩陣來存儲，那絕大部分的存儲空間都被浪費了。

但這也并不是說，鄰接矩陣的存儲方法就完全沒有優點。首先，鄰接矩陣的存儲方式簡單、直接，因為基于數組，所以在獲取兩個頂點的關系時，就非常高效。其次，用鄰接矩陣存儲圖的另外一個好處是方便計算。這是因為，用鄰接矩陣的方式存儲圖，可以將很多圖的運算轉換成矩陣之間的運算。比如求解最短路徑問題時會提到一個Floyd-Warshall 算法，就是利用矩陣循環相乘若干次得到結果。

鄰接表存儲方法

鄰接表（Adjacency List）。

鄰接表是不是有點像散列表？每個頂點對應一條鏈表，鏈表中存儲的是與這個頂點相連接的其他頂點。

圖中畫的是一個有向圖的鄰接表存儲方式，每個頂點對應的鏈表里面，存儲的是指向的頂點。對于無向圖來說，也是類似的，不過，每個頂點的鏈表中存儲的，是跟這個頂點有邊相連的頂點，你可以自己畫下。

鄰接矩陣存儲起來比較浪費空間，但是使用起來比較節省時間。相反，鄰接表存儲起來比較節省空間，但是使用起來就比較耗時間。

就像圖中的例子，如果我們要確定，是否存在一條從頂點 2 到頂點 4 的邊，那我們就要遍歷頂點 2 對應的那條鏈表，看鏈表中是否存在頂點 4。而且，我們前面也講過，鏈表的存儲方式對緩存不友好。所以，比起鄰接矩陣的存儲方式，在鄰接表中查詢兩個頂點之間的關系就沒那么高效了。

在散列表那幾節里，我講到，在基于鏈表法解決沖突的散列表中，如果鏈過長，為了提高查找效率，我們可以將鏈表換成其他更加高效的數據結構，比如平衡二叉查找樹等。我們剛剛也講到，鄰接表長得很像散列。所以，我們也可以將鄰接表同散列表一樣進行“改進升級”。

我們可以將鄰接表中的鏈表改成平衡二叉查找樹。實際開發中，我們可以選擇用紅黑樹。這樣，我們就可以更加快速地查找兩個頂點之間是否存在邊了。當然，這里的二叉查找樹可以換成其他動態數據結構，比如跳表、散列表等。除此之外，我們還可以將鏈表改成有序動態數組，可以通過二分查找的方法來快速定位兩個頂點之間否是存在邊。

如何存儲微博、微信等社交網絡中的好友關系？

數據結構是為算法服務的，所以具體選擇哪種存儲方法，與期望支持的操作有關系。針對微博用戶關系，假設我們需要支持下面這樣幾個操作：

• 判斷用戶 A 是否關注了用戶 B；
• 判斷用戶 A 是否是用戶 B 的粉絲；
• 用戶 A 關注用戶 B；
• 用戶 A 取消關注用戶 B；
• 根據用戶名稱的首字母排序，分頁獲取用戶的粉絲列表；
• 根據用戶名稱的首字母排序，分頁獲取用戶的關注列表。

關于如何存儲一個圖，前面我們講到兩種主要的存儲方法，鄰接矩陣和鄰接表。因為社交網絡是一張稀疏圖，使用鄰接矩陣存儲比較浪費存儲空間。所以，這里我們采用鄰接表來存儲。

不過，用一個鄰接表來存儲這種有向圖是不夠的。我們去查找某個用戶關注了哪些用戶非常容易，但是如果要想知道某個用戶都被哪些用戶關注了，也就是用戶的粉絲列表，是非常困難的。

基于此，我們需要一個逆鄰接表。鄰接表中存儲了用戶的關注關系，逆鄰接表中存儲的是用戶的被關注關系。對應到圖上，鄰接表中，每個頂點的鏈表中，存儲的就是這個頂點指向的頂點，逆鄰接表中，每個頂點的鏈表中，存儲的是指向這個頂點的頂點。如果要查找某個用戶關注了哪些用戶，我們可以在鄰接表中查找；如果要查找某個用戶被哪些用戶關注了，我們從逆鄰接表中查找。

基礎的鄰接表不適合快速判斷兩個用戶之間是否是關注與被關注的關系，所以我們選擇改進版本，將鄰接表中的鏈表改為支持快速查找的動態數據結構。選擇哪種動態數據結構呢？紅黑樹、跳表、有序動態數組還是散列表呢？

因為我們需要按照用戶名稱的首字母排序，分頁來獲取用戶的粉絲列表或者關注列表，用跳表這種結構再合適不過了。這是因為，跳表插入、刪除、查找都非常高效，時間復雜度是 O(logn)，空間復雜度上稍高，是 O(n)。最重要的一點，跳表中存儲的數據本來就是有序的了，分頁獲取粉絲列表或關注列表，就非常高效。

如果對于小規模的數據，比如社交網絡中只有幾萬、幾十萬個用戶，我們可以將整個社交關系存儲在內存中，上面的解決思路是沒有問題的。但是如果像微博那樣有上億的用戶，數據規模太大，我們就無法全部存儲在內存中了。這個時候該怎么辦呢？

我們可以通過哈希算法等數據分片方式，將鄰接表存儲在不同的機器上。你可以看下面這幅圖，我們在機器 1 上存儲頂點 1，2，3 的鄰接表，在機器 2 上，存儲頂點 4，5 的鄰接表。逆鄰接表的處理方式也一樣。當要查詢頂點與頂點關系的時候，我們就利用同樣的哈希算法，先定位頂點所在的機器，然后再在相應的機器上查找。

另外一種解決思路，就是利用外部存儲（比如硬盤），因為外部存儲的存儲空間要比內存會寬裕很多。數據庫是我們經常用來持久化存儲關系數據的，所以我這里介紹一種數據庫的存儲方式。

我用下面這張表來存儲這樣一個圖。為了高效地支持前面定義的操作，我們可以在表上建立多個索引，比如第一列、第二列，給這兩列都建立索引。

微信好友關系存儲方式。無向圖，也可以使用鄰接表的方式存儲每個人所對應的好友列表。為了支持快速查找，好友列表可以使用紅黑樹存儲。

字符串匹配算法之

比較簡單的、好理解的，它們分別是：BF 算法和 RK 算法。單模式串匹配的算法，一個串跟一個串進行匹配。

比較難理解、但更加高效的，它們是：BM 算法和 KMP 算法。在一個串中同時查找多個串，它們分別是 Trie 樹和 AC 自動機。

RK 算法是 BF 算法的改進，它巧妙借助了我們前面講過的哈希算法，讓匹配的效率有了很大的提升。那RK 算法是如何借助哈希算法來實現高效字符串匹配的呢？

BF 算法

BF 算法中文叫作暴力匹配算法，也叫樸素匹配算法。從名字可以看出，這種算法的字符串匹配方式很“暴力”，當然也就會比較簡單、好懂，但相應的性能也不高。

先定義兩個概念，分別是主串和模式串。（在A中查找B，A主串，長度n；B模式串，長度m）

，BF 算法的思想可以用一句話來概括，我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。

在極端情況下，比如主串是“aaaaa…aaaaaa”（省略號表示有很多重復的字符 a），模式串是“aaaaab”。我們每次都比對 m 個字符，要比對 n-m+1 次，所以，這種算法的最壞情況時間復雜度是 O(n*m)。

盡管理論上，BF 算法的時間復雜度很高，是 O(n*m)，但在實際的開發中，它卻是一個比較常用的字符串匹配算法。為什么這么說呢？原因有兩點。

第一，實際的軟件開發中，大部分情況下，模式串和主串的長度都不會太長。而且每次模式串與主串中的子串匹配的時候，當中途遇到不能匹配的字符的時候，就可以就停止了，不需要把 m 個字符都比對一下。所以，盡管理論上的最壞情況時間復雜度是 O(n*m)，但是，統計意義上，大部分情況下，算法執行效率要比這個高很多。

第二，樸素字符串匹配算法思想簡單，代碼實現也非常簡單。簡單意味著不容易出錯，如果有 bug 也容易暴露和修復。在工程中，在滿足性能要求的前提下，簡單是首選。這也是我們常說的KISS（Keep it Simple and Stupid）設計原則。

所以，在實際的軟件開發中，絕大部分情況下，樸素的字符串匹配算法就夠用了。

RK 算法

RK 算法，其實就是剛剛講的 BF 算法的升級版。

BF 算法，如果模式串長度為 m，主串長度為 n，那在主串中，就會有 n-m+1 個長度為 m 的子串，我們只需要暴力地對比這 n-m+1 個子串與模式串，就可以找出主串與模式串匹配的子串。

但是，每次檢查主串與子串是否匹配，需要依次比對每個字符，所以 BF 算法的時間復雜度就比較高，是 O(n*m)。我們對樸素的字符串匹配算法稍加改造，引入哈希算法，時間復雜度立刻就會降低。

RK 算法的思路是這樣的：

我們通過哈希算法對主串中的 n-m+1 個子串分別求哈希值，然后逐個與模式串的哈希值比較大小。如果某個子串的哈希值與模式串相等，那就說明對應的子串和模式串匹配了（這里先不考慮哈希沖突的問題，后面我們會講到）。因為哈希值是一個數字，數字之間比較是否相等是非常快速的，所以模式串和子串比較的效率就提高了。

不過，通過哈希算法計算子串的哈希值的時候，我們需要遍歷子串中的每個字符。盡管模式串與子串比較的效率提高了，但是，算法整體的效率并沒有提高。有沒有方法可以提高哈希算法計算子串哈希值的效率呢？

這就需要哈希算法設計的非常有技巧了。我們假設要匹配的字符串的字符集中只包含 K 個字符，我們可以用一個 K 進制數來表示一個子串，這個 K 進制數轉化成十進制數，作為子串的哈希值。表述起來有點抽象，我舉了一個例子，看完你應該就能懂了。

比如要處理的字符串只包含 a～z 這 26 個小寫字母，那我們就用二十六進制來表示一個字符串。我們把 a～z 這 26 個字符映射到 0～25 這 26 個數字，a 就表示 0，b 就表示 1，以此類推，z 表示 25。

在十進制的表示法中，一個數字的值是通過下面的方式計算出來的。對應到二十六進制，一個包含 a 到 z 這 26 個字符的字符串，計算哈希的時候，我們只需要把進位從 10 改成 26 就可以。

這個哈希算法你應該看懂了吧？現在，為了方便解釋，在下面的講解中，我假設字符串中只包含 a～z 這 26 個小寫字符，我們用二十六進制來表示一個字符串，對應的哈希值就是二十六進制數轉化成十進制的結果。

這種哈希算法有一個特點，在主串中，相鄰兩個子串的哈希值的計算公式有一定關系。我這有個個例子，你先找一下規律，再來看我后面的講解。

從這里例子中，我們很容易就能得出這樣的規律：相鄰兩個子串 s[i-1] 和 s[i]（i 表示子串在主串中的起始位置，子串的長度都為 m），對應的哈希值計算公式有交集，也就是說，我們可以使用 s[i-1] 的哈希值很快的計算出 s[i] 的哈希值。如果用公式表示的話，就是下面這個樣子：

不過，這里有一個小細節需要注意，那就是 26^(m-1) 這部分的計算，我們可以通過查表的方法來提高效率。我們事先計算好 26^0、261、26^2……26(m-1)，并且存儲在一個長度為 m 的數組中，公式中的“次方”就對應數組的下標。當我們需要計算 26 的 x 次方的時候，就可以從數組的下標為 x 的位置取值，直接使用，省去了計算的時間。

我們開頭的時候提過，RK 算法的效率要比 BF 算法高，現在，我們就來分析一下，RK 算法的時間復雜度到底是多少呢？

整個 RK 算法包含兩部分，計算子串哈希值和模式串哈希值與子串哈希值之間的比較。第一部分，我們前面也分析了，可以通過設計特殊的哈希算法，只需要掃描一遍主串就能計算出所有子串的哈希值了，所以這部分的時間復雜度是 O(n)。

模式串哈希值與每個子串哈希值之間的比較的時間復雜度是 O(1)，總共需要比較 n-m+1 個子串的哈希值，所以，這部分的時間復雜度也是 O(n)。所以，RK 算法整體的時間復雜度就是 O(n)。

這里還有一個問題就是，模式串很長，相應的主串中的子串也會很長，通過上面的哈希算法計算得到的哈希值就可能很大，如果超過了計算機中整型數據可以表示的范圍，那該如何解決呢？

剛剛我們設計的哈希算法是沒有散列沖突的，也就是說，一個字符串與一個二十六進制數一一對應，不同的字符串的哈希值肯定不一樣。因為我們是基于進制來表示一個字符串的，你可以類比成十進制、十六進制來思考一下。實際上，我們為了能將哈希值落在整型數據范圍內，可以犧牲一下，允許哈希沖突。這個時候哈希算法該如何設計呢？

哈希算法的設計方法有很多，我舉一個例子說明一下。假設字符串中只包含 a～z 這 26 個英文字母，那我們每個字母對應一個數字，比如 a 對應 1，b 對應 2，以此類推，z 對應 26。我們可以把字符串中每個字母對應的數字相加，最后得到的和作為哈希值。這種哈希算法產生的哈希值的數據范圍就相對要小很多了。

不過，你也應該發現，這種哈希算法的哈希沖突概率也是挺高的。當然，我只是舉了一個最簡單的設計方法，還有很多更加優化的方法，比如將每一個字母從小到大對應一個素數，而不是 1，2，3……這樣的自然數，這樣沖突的概率就會降低一些。

那現在新的問題來了。之前我們只需要比較一下模式串和子串的哈希值，如果兩個值相等，那這個子串就一定可以匹配模式串。但是，當存在哈希沖突的時候，有可能存在這樣的情況，子串和模式串的哈希值雖然是相同的，但是兩者本身并不匹配。

實際上，解決方法很簡單。當我們發現一個子串的哈希值跟模式串的哈希值相等的時候，我們只需要再對比一下子串和模式串本身就好了。當然，如果子串的哈希值與模式串的哈希值不相等，那對應的子串和模式串肯定也是不匹配的，就不需要比對子串和模式串本身了。

RK 算法是借助哈希算法對 BF 算法進行改造，即對每個子串分別求哈希值，然后拿子串的哈希值與模式串的哈希值比較，減少了比較的時間。所以，理想情況下，RK 算法的時間復雜度是 O(n)，跟 BF 算法相比，效率提高了很多。不過這樣的效率取決于哈希算法的設計方法，如果存在沖突的情況下，時間復雜度可能會退化。極端情況下，哈希算法大量沖突，時間復雜度就退化為 O(n*m)。但也不要太悲觀，一般情況下，沖突不會很多，RK 算法的效率還是比 BF 算法高的。

BM 算法

BM算法原理

BM算法定義了兩個規則：

壞字符規則：當文本串中的某個字符跟模式串的某個字符不匹配時，我們稱文本串中的這個失配字符為壞字符，此時模式串需要向右移動，移動的位數 = 壞字符在模式串中的位置 - 壞字符在模式串中最右出現的位置。此外，如果"壞字符"不包含在模式串之中，則最右出現位置為-1。
好后綴規則：當字符失配時，后移位數 = 好后綴在模式串中的位置 - 好后綴在模式串上一次出現的位置，且如果好后綴在模式串中沒有再次出現，則為-1。

下面舉例說明BM算法。例如，給定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，現要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

• 首先，“文本串"與"模式串"頭部對齊，從尾部開始比較。”S“與”E“不匹配。這時，”S“就被稱為"壞字符”（bad character），即不匹配的字符，它對應著模式串的第6位。且"S“不包含在模式串”EXAMPLE“之中（相當于最右出現位置是-1），這意味著可以把模式串后移6-(-1)=7位，從而直接移到”S"的后一位。
  

• 依然從尾部開始比較，發現"P“與”E“不匹配，所以”P“是"壞字符”。但是，"P“包含在模式串”EXAMPLE"之中。因為“P”這個“壞字符”對應著模式串的第6位（從0開始編號），且在模式串中的最右出現位置為4，所以，將模式串后移6-4=2位，兩個"P"對齊。

• 依次比較，得到 “MPLE”匹配，稱為"好后綴"（good suffix），即所有尾部匹配的字符串。注意，“MPLE”、“PLE”、“LE”、"E"都是好后綴。

• 發現“I”與“A”不匹配：“I”是壞字符。如果是根據壞字符規則，此時模式串應該后移2-(-1)=3位。問題是，有沒有更優的移法？

• 更優的移法是利用好后綴規則：當字符失配時，后移位數 = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現的位置，且如果好后綴在模式串中沒有再次出現，則為-1。所有的“好后綴”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的頭部出現，所以后移6-0=6位。可以看出，“壞字符規則”只能移3位，“好后綴規則”可以移6位。每次后移這兩個規則之中的較大值。這兩個規則的移動位數，只與模式串有關，與原文本串無關。

• 繼續從尾部開始比較，“P”與“E”不匹配，因此“P”是“壞字符”，根據“壞字符規則”，后移 6 - 4 = 2位。因為是最后一位就失配，尚未獲得好后綴。

好后綴加深理解

由上可知，BM算法不僅效率高，而且構思巧妙，容易理解。壞字符規則相對而言比較好理解，好后綴如果還不理解，我這里再繼續舉個例子解釋一下，這里加深理解。

• 如果模式串中存在已經匹配成功的好后綴，則把目標串與好后綴對齊，然后從模式串的最尾元素開始往前匹配。

• 如果無法找到匹配好的后綴，找一個匹配的最長的前綴，讓目標串與最長的前綴對齊（如果這個前綴存在的話）。模式串[m-s，m] = 模式串[0，s] 。

• 如果完全不存在和好后綴匹配的子串，則右移整個模式串。

先實現好字符規則

BM算法還是很好理解的，其實如果你之前學習KMP算法你也會有同樣的感受，KMP算法理解起來不是很難，但是重點在于怎么去實現next數組。BM算法也是，原理理解起來其實非常的容易，不過怎么去實現，沒有一套標準的代碼。不過可以研究別人的代碼，然后實現一套盡量適合精簡的代碼。還是一樣，一步一步來，我們先來實現好字符規則。好字符規則的代碼如下，我會在代碼中必要的地方加入注釋，輔助理解，代碼是最好的老師。

public static void getRight(String pat, int[] right) {//首先創建一個模式串的字符位置的數組，初始化為-1，就是用于記錄模式串//中，每個字符在模式串中的相對位置，這里直接用的是256，也//就是ASCII碼的最大值，當然，如果你的字符串中只限制了26個//字符，你也可以直接使用26for (int i = 0; i < 256; i++) {right[i] = -1;}//值得一提的是，通過這種方式，可以你會發現，如果模式串中存在相同的//字符，那么right數組中，記錄的是最右的那個字符的位置for (int j = 0; j < pat.length(); j++) {right[pat.charAt(j)] = j;} }public static int Search(String txt, String pat, int[] right) {int M = txt.length();//主串的長度int N = pat.length();//模式串的長度int skip;//用于記錄跳過幾個字符for (int i = 0; i < M - N; i += skip) {skip = 0;//每次進入循環要記得初始化為0for (int j = N - 1; j >= 0; j--) {//不相等，意味著出現壞字符，按照上面的規則移動if (pat.charAt(j) != txt.charAt(i + j)) {skip = j - right[txt.charAt(i + j)];//skip之所以會小于1，可能是因為壞字符在模式串中最右的位置，可能//在j指向字符的右側，就是已經越過了。if (skip < 1) skip = 1;break;}}//注意了這個時候循環了一遍之后，skip如果等于0，意味著沒有壞字符出現，所以//匹配成功，返回當前字符i的位置if (skip == 0)return i;}return -1; }

完整BM實現

上面的代碼不難理解，相信你已經看懂了，那么接下來也不用單獨來講好后綴的實現，直接上完整的實現代碼。因為完整的BM實現中，就是比較壞字符規則以及好后綴規則，哪個移動的字符數更多，就使用哪個。老樣子，下面的代碼中我盡量的加注釋。

public static int pattern(String pattern, String target) {int tLen = target.length();//主串的長度int pLen = pattern.length();//模式串的長度//如果模式串比主串長，沒有可比性，直接返回-1if (pLen > tLen) {return -1;}int[] bad_table = build_bad_table(pattern);// 獲得壞字符數值的數組，實現看下面int[] good_table = build_good_table(pattern);// 獲得好后綴數值的數組，實現看下面for (int i = pLen - 1, j; i < tLen;) {System.out.println("跳躍位置：" + i);//這里和上面實現壞字符的時候不一樣的地方，我們之前提前求出壞字符以及好后綴//對應的數值數組，所以，我們只要在一邊循環中進行比較。還要說明的一點是，這里//沒有使用skip記錄跳過的位置，直接針對主串中移動的指針i進行移動for (j = pLen - 1; target.charAt(i) == pattern.charAt(j); i--, j--) {if (j == 0) {//指向模式串的首字符，說明匹配成功，直接返回就可以了System.out.println("匹配成功，位置：" + i);//如果你還要匹配不止一個模式串，那么這里直接跳出這個循環，并且讓i++//因為不能直接跳過整個已經匹配的字符串，這樣的話可能會丟失匹配。 // i++; // 多次匹配 // break;return i;}}//如果出現壞字符，那么這個時候比較壞字符以及好后綴的數組，哪個大用哪個i += Math.max(good_table[pLen - j - 1], bad_table[target.charAt(i)]);}return -1; }//字符信息表 public static int[] build_bad_table(String pattern) {final int table_size = 256;//上面已經解釋過了，字符的種類int[] bad_table = new int[table_size];//創建一個數組，用來記錄壞字符出現時，應該跳過的字符數int pLen = pattern.length();//模式串的長度for (int i = 0; i < bad_table.length; i++) {bad_table[i] = pLen; //默認初始化全部為匹配字符串長度,因為當主串中的壞字符在模式串中沒有出//現時，直接跳過整個模式串的長度就可以了}for (int i = 0; i < pLen - 1; i++) {int k = pattern.charAt(i);//記錄下當前的字符ASCII碼值//這里其實很值得思考一下，bad_table就不多說了，是根據字符的ASCII值存儲//壞字符出現最右的位置，這在上面實現壞字符的時候也說過了。不過你仔細思考//一下，為什么這里存的壞字符數值，是最右的那個壞字符相對于模式串最后一個//字符的位置？為什么？首先你要理解i的含義，這個i不是在這里的i，而是在上面//那個pattern函數的循環的那個i，為了方便我們稱呼為I，這個I很神奇，雖然I是//在主串上的指針，但是由于在循環中沒有使用skip來記錄，直接使用I隨著j匹配//進行移動，也就意味著，在某種意義上，I也可以直接定位到模式串的相對位置，//理解了這一點，就好理解在本循環中，i的行為了。//其實仔細去想一想，我們分情況來思考，如果模式串的最//后一個字符，也就是匹配開始的第一個字符，出現了壞字符，那么這個時候，直//接移動這個數值，那么正好能讓最右的那個字符正對壞字符。那么如果不是第一個//字符出現壞字符呢？這種情況你仔細想一想，這種情況也就意味著出現了好后綴的//情況，假設我們將最右的字符正對壞字符bad_table[k] = pLen - 1 - i;}return bad_table; }//匹配偏移表 public static int[] build_good_table(String pattern) {int pLen = pattern.length();//模式串長度int[] good_table = new int[pLen];//創建一個數組，存好后綴數值//用于記錄最新前綴的相對位置，初始化為模式串長度，因為意思就是當前后綴字符串為空//要明白lastPrefixPosition 的含義int lastPrefixPosition = pLen;for (int i = pLen - 1; i >= 0; --i) {if (isPrefix(pattern, i + 1)) {//如果當前的位置存在前綴匹配，那么記錄當前位置lastPrefixPosition = i + 1;}good_table[pLen - 1 - i] = lastPrefixPosition - i + pLen - 1;}for (int i = 0; i < pLen - 1; ++i) {//計算出指定位置匹配的后綴的字符串長度int slen = suffixLength(pattern, i);good_table[slen] = pLen - 1 - i + slen;}return good_table; }//前綴匹配 private static boolean isPrefix(String pattern, int p) {int patternLength = pattern.length();//模式串長度//這里j從模式串第一個字符開始，i從指定的字符位置開始，通過循環判斷當前指定的位置p//之后的字符串是否匹配模式串前綴for (int i = p, j = 0; i < patternLength; ++i, ++j) {if (pattern.charAt(i) != pattern.charAt(j)) {return false;}}return true; }//后綴匹配 private static int suffixLength(String pattern, int p) {int pLen = pattern.length();int len = 0;for (int i = p, j = pLen - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) {len += 1;}return len; }

理解一下上面代碼，這里我針對上面代碼舉個例子，計算之后的兩張表的數值如下：

版權聲明：本文為CSDN博主「BoCong-Deng」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/DBC_121/article/details/105569440

KMP算法

KMP算法是一種字符串匹配算法，可以在 O(n+m) 的時間復雜度內實現兩個字符串的匹配。本文將引導您學習KMP算法，閱讀大約需要30分鐘。

字符串匹配問題

所謂字符串匹配，是這樣一種問題：“字符串 P 是否為字符串 S 的子串？如果是，它出現在 S 的哪些位置？” 其中 S 稱為**主串；P 稱為模式串**。下面的圖片展示了一個例子。

主串是莎翁那句著名的 “to be or not to be”，這里刪去了空格。“no” 這個模式串的匹配結果是“出現了一次，從S[6]開始”；“ob”這個模式串的匹配結果是“出現了兩次，分別從s[1]、s[10]開始”。按慣例，主串和模式串都以0開始編號。
　　字符串匹配是一個非常頻繁的任務。例如，今有一份名單，你急切地想知道自己在不在名單上；又如，假設你拿到了一份文獻，你希望快速地找到某個關鍵字（keyword）所在的章節……凡此種種，不勝枚舉。
　　我們先從最樸素的Brute-Force算法開始講起。

Brute-Force

顧名思義，Brute-Force是一個純暴力算法。說句題外話，我懷疑，“暴力”一詞在算法領域表示“窮舉、極低效率的實現”，可能就是源于這個英文詞。
　　首先，我們應該如何實現兩個字符串 A,B 的比較？所謂字符串比較，就是問“兩個字符串是否相等”。最樸素的思想，就是從前往后逐字符比較，一旦遇到不相同的字符，就返回False；如果兩個字符串都結束了，仍然沒有出現不對應的字符，則返回True。實現如下：

既然我們可以知道“兩個字符串是否相等”，那么最樸素的字符串匹配算法 Brute-Force 就呼之欲出了——

• 枚舉 i = 0, 1, 2 … , len(S)-len§
• 將 S[i : i+len§] 與 P 作比較。如果一致，則找到了一個匹配。

現在我們來模擬 Brute-Force 算法，對主串 “AAAAAABC” 和模式串 “AAAB” 做匹配：

這是一個清晰明了的算法，實現也極其簡單。下面給出Python和C++的實現：

我們成功實現了 Brute-Force 算法。現在，我們需要對它的時間復雜度做一點討論。按照慣例，記 n = |S| 為串 S 的長度，m = |P| 為串 P 的長度。
　　考慮“字符串比較”這個小任務的復雜度。最壞情況發生在：兩個字符串唯一的差別在最后一個字符。這種情況下，字符串比較必須走完整個字符串，才能給出結果，因此復雜度是 O(len) 的。

由此，不難想到 Brute-Force 算法所面對的最壞情況：主串形如“AAAAAAAAAAA…B”，而模式串形如“AAAAA…B”。每次字符串比較都需要付出 |P| 次字符比較的代價，總共需要比較 |S| - |P| + 1次，因此總時間復雜度是 O(|P|?(|S|?|P|+1))O(|P|\cdot (|S| - |P| + 1) )O(|P|\cdot (|S| - |P| + 1) ) . 考慮到主串一般比模式串長很多，故 Brute-Force 的復雜度是 O(|P|?|S|)O(|P| \cdot |S|)O(|P| \cdot |S|) ，也就是 O(nm)的。這太慢了！

Brute-Force的改進思路

經過剛剛的分析，您已經看到，Brute-Force 慢得像爬一樣。它最壞的情況如下圖所示：

我們很難降低字符串比較的復雜度（因為比較兩個字符串，真的只能逐個比較字符）。因此，我們考慮降低比較的趟數。如果比較的趟數能降到足夠低，那么總的復雜度也將會下降很多。　　要優化一個算法，首先要回答的問題是“我手上有什么信息？”　我們手上的信息是否足夠、是否有效，決定了我們能把算法優化到何種程度。請記住：盡可能利用殘余的信息，是KMP算法的思想所在。
　　在 Brute-Force 中，如果從 S[i] 開始的那一趟比較失敗了，算法會直接開始嘗試從 S[i+1] 開始比較。這種行為，屬于典型的“沒有從之前的錯誤中學到東西”。我們應當注意到，一次失敗的匹配，會給我們提供寶貴的信息——如果 S[i : i+len§] 與 P 的匹配是在第 r 個位置失敗的，那么從 S[i] 開始的 (r-1) 個連續字符，一定與 P 的前 (r-1) 個字符一模一樣！

需要實現的任務是“字符串匹配”，而每一次失敗都會給我們換來一些信息——能告訴我們，主串的某一個子串等于模式串的某一個前綴。但是這又有什么用呢？

跳過不可能成功的字符串比較

有些趟字符串比較是有可能會成功的；有些則毫無可能。我們剛剛提到過，優化 Brute-Force 的路線是“盡量減少比較的趟數”，而如果我們跳過那些絕不可能成功的字符串比較，則可以希望復雜度降低到能接受的范圍。
　　那么，哪些字符串比較是不可能成功的？來看一個例子。已知信息如下：

• 模式串 P = “abcabd”.
• 和主串從S[0]開始匹配時，在 P[5] 處失配。

首先，利用上一節的結論。既然是在 P[5] 失配的，那么說明 S[0:5] 等于 P[0:5]，即"abcab". 現在我們來考慮：從 S[1]、S[2]、S[3] 開始的匹配嘗試，有沒有可能成功？
　　從 S[1] 開始肯定沒辦法成功，因為 S[1] = P[1] = ‘b’，和 P[0] 并不相等。從 S[2] 開始也是沒戲的，因為 S[2] = P[2] = ‘c’，并不等于P[0]. 但是從 S[3] 開始是有可能成功的——至少按照已知的信息，我們推不出矛盾。

帶著“跳過不可能成功的嘗試”的思想，我們來看next數組。

next數組

next數組是對于模式串而言的。P 的 next 數組定義為：next[i] 表示 P[0] ~ P[i] 這一個子串，使得 前k個字符恰等于后k個字符 的最大的k. 特別地，k不能取i+1（因為這個子串一共才 i+1 個字符，自己肯定與自己相等，就沒有意義了）。

上圖給出了一個例子。P=“abcabd"時，next[4]=2，這是因為P[0] ~ P[4] 這個子串是"abcab”，前兩個字符與后兩個字符相等，因此next[4]取2. 而next[5]=0，是因為"abcabd"找不到前綴與后綴相同，因此只能取0.

如果把模式串視為一把標尺，在主串上移動，那么 Brute-Force 就是每次失配之后只右移一位；改進算法則是每次失配之后，移很多位，跳過那些不可能匹配成功的位置。但是該如何確定要移多少位呢？

在 S[0] 嘗試匹配，失配于 S[3] <=> P[3] 之后，我們直接把模式串往右移了兩位，讓 S[3] 對準 P[1]. 接著繼續匹配，失配于 S[8] <=> P[6], 接下來我們把 P 往右平移了三位，把 S[8] 對準 P[3]. 此后繼續匹配直到成功。
　　我們應該如何移動這把標尺？很明顯，如圖中藍色箭頭所示，舊的后綴要與新的前綴一致（如果不一致，那就肯定沒法匹配上了）！

回憶next數組的性質：P[0] 到 P[i] 這一段子串中，前next[i]個字符與后next[i]個字符一模一樣。既然如此，如果失配在 P[r], 那么P[0]~P[r-1]這一段里面，前next[r-1]個字符恰好和后next[r-1]個字符相等——也就是說，我們可以拿長度為 next[r-1] 的那一段前綴，來頂替當前后綴的位置，讓匹配繼續下去！
　　您可以驗證一下上面的匹配例子：P[3]失配后，把P[next[3-1]]也就是P[1]對準了主串剛剛失配的那一位；P[6]失配后，把P[next[6-1]]也就是P[3]對準了主串剛剛失配的那一位。

如上圖所示，綠色部分是成功匹配，失配于紅色部分。深綠色手繪線條標出了相等的前綴和后綴，其長度為next[右端]. 由于手繪線條部分的字符是一樣的，所以直接把前面那條移到后面那條的位置。因此說，next數組為我們如何移動標尺提供了依據。接下來，我們實現這個優化的算法。

利用next數組進行匹配

了解了利用next數組加速字符串匹配的原理，我們接下來代碼實現之。分為兩個部分：建立next數組、利用next數組進行匹配。
　　首先是建立next數組。我們暫且用最樸素的做法，以后再回來優化：

如上圖代碼所示，直接根據next數組的定義來建立next數組。不難發現它的復雜度是 O(m2)O(m^2)O(m2) 的。
　　接下來，實現利用next數組加速字符串匹配。代碼如下：

如何分析這個字符串匹配的復雜度呢？乍一看，pos值可能不停地變成next[pos-1]，代價會很高；但我們使用攤還分析，顯然pos值一共頂多自增len(S)次，因此pos值減少的次數不會高于len(S)次。由此，復雜度是可以接受的，不難分析出整個匹配算法的時間復雜度：O(n+m).

快速求next數組

終于來到了我們最后一個問題——如何快速構建next數組。
　　首先說一句：快速構建next數組，是KMP算法的精髓所在，核心思想是“P自己與自己做匹配”。
　　為什么這樣說呢？回顧next數組的完整定義：

• 定義 “k-前綴” 為一個字符串的前 k 個字符； “k-后綴” 為一個字符串的后 k 個字符。k 必須小于字符串長度。
• next[x] 定義為： P[0]~P[x] 這一段字符串，使得k-前綴恰等于k-后綴的最大的k.

這個定義中，不知不覺地就包含了一個匹配——前綴和后綴相等。接下來，我們考慮采用遞推的方式求出next數組。如果next[0], next[1], … next[x-1]均已知，那么如何求出 next[x] 呢？

來分情況討論。首先，已經知道了 next[x-1]（以下記為now），如果 P[x] 與 P[now] 一樣，那最長相等前后綴的長度就可以擴展一位，很明顯 next[x] = now + 1. 圖示如下。

剛剛解決了 P[x] = P[now] 的情況。那如果 P[x] 與 P[now] 不一樣，又該怎么辦？

如圖。長度為 now 的子串 A 和子串 B 是 P[0]~P[x-1] 中最長的公共前后綴。可惜 A 右邊的字符和 B 右邊的那個字符不相等，next[x]不能改成 now+1 了。因此，我們應該縮短這個now，把它改成小一點的值，再來試試 P[x] 是否等于 P[now].
　　now該縮小到多少呢？顯然，我們不想讓now縮小太多。因此我們決定，在保持“P[0]~P[x-1]的now-前綴仍然等于now-后綴”的前提下，讓這個新的now盡可能大一點。 P[0]~P[x-1] 的公共前后綴，前綴一定落在串A里面、后綴一定落在串B里面。換句話講：接下來now應該改成：使得 A的k-前綴等于B的k-后綴 的最大的k.
　　您應該已經注意到了一個非常強的性質——串A和串B是相同的！B的后綴等于A的后綴！因此，使得A的k-前綴等于B的k-后綴的最大的k，其實就是串A的最長公共前后綴的長度 —— next[now-1]！

來看上面的例子。當P[now]與P[x]不相等的時候，我們需要縮小now——把now變成next[now-1]，直到P[now]=P[x]為止。P[now]=P[x]時，就可以直接向右擴展了。

代碼實現如下：

應用攤還分析，不難證明構建next數組的時間復雜度是O(m)的。至此，我們以O(n+m)的時間復雜度，實現了構建next數組、利用next數組進行字符串匹配。

以上就是KMP算法。它于1977年被提出，全稱 Knuth–Morris–Pratt 算法。讓我們記住前輩們的名字：Donald Knuth(K), James H. Morris(M), Vaughan Pratt§.
　　希望本文對你有幫助。 本文在我博客的url是 https://ruanx.pw/kmp/ , 以后可能會更新。

---

最后附上洛谷P3375 【模板】KMP字符串匹配 的Python和Java版代碼：

轉載自：

作者：阮行止
鏈接：如何更好地理解和掌握 KMP 算法? - 阮行止的回答 - 知乎
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

Trie樹

搜索引擎的搜索關鍵詞提示功能，我想你應該不陌生吧？為了方便快速輸入，當你在搜索引擎的搜索框中，輸入要搜索的文字的某一部分的時候，搜索引擎就會自動彈出下拉框，里面是各種關鍵詞提示。

什么是“Trie 樹”？

Trie 樹，也叫“字典樹”。顧名思義，它是一個樹形結構。它是一種專門處理字符串匹配的數據結構，用來解決在一組字符串集合中快速查找某個字符串的問題。

當然，這樣一個問題可以有多種解決方法，比如散列表、紅黑樹，或者我們前面幾節講到的一些字符串匹配算法，但是，Trie 樹在這個問題的解決上，有它特有的優點。不僅如此，Trie 樹能解決的問題也不限于此，我們一會兒慢慢分析。

現在，我們先來看下，Trie 樹到底長什么樣子。

我舉個簡單的例子來說明一下。我們有 6 個字符串，它們分別是：how，hi，her，hello，so，see。我們希望在里面多次查找某個字符串是否存在。如果每次查找，都是拿要查找的字符串跟這 6 個字符串依次進行字符串匹配，那效率就比較低，有沒有更高效的方法呢？

這個時候，我們就可以先對這 6 個字符串做一下預處理，組織成 Trie 樹的結構，之后每次查找，都是在 Trie 樹中進行匹配查找。Trie 樹的本質，就是利用字符串之間的公共前綴，將重復的前綴合并在一起。最后構造出來的就是下面這個圖中的樣子。

根節點不包含任何信息。每個節點表示一個字符串中的字符，從根節點到紅色節點的一條路徑表示一個字符串（注意：紅色節點并不都是葉子節點）。

Trie 樹構造的分解過程。構造過程的每一步，都相當于往 Trie 樹中插入一個字符串。當所有字符串都插入完成之后，Trie 樹就構造好了。

如何實現一棵 Trie 樹？

知道了 Trie 樹長什么樣子，我們現在來看下，如何用代碼來實現一個 Trie 樹。

從剛剛 Trie 樹的介紹來看，Trie 樹主要有兩個操作，一個是將字符串集合構造成 Trie 樹。這個過程分解開來的話，就是一個將字符串插入到 Trie 樹的過程。另一個是在 Trie 樹中查詢一個字符串。

了解了 Trie 樹的兩個主要操作之后，我們再來看下，如何存儲一個 Trie 樹？

從前面的圖中，我們可以看出，Trie 樹是一個多叉樹。我們知道，二叉樹中，一個節點的左右子節點是通過兩個指針來存儲的，如下所示 Java 代碼。那對于多叉樹來說，我們怎么存儲一個節點的所有子節點的指針呢？

class BinaryTreeNode {char data;BinaryTreeNode left;BinaryTreeNode right; }

我先介紹其中一種存儲方式，也是經典的存儲方式，大部分數據結構和算法書籍中都是這么講的。還記得我們前面講到的散列表嗎？借助散列表的思想，我們通過一個下標與字符一一映射的數組，來存儲子節點的指針。這句話稍微有點抽象，不怎么好懂，我畫了一張圖你可以看看。

假設我們的字符串中只有從 a 到 z 這 26 個小寫字母，我們在數組中下標為 0 的位置，存儲指向子節點 a 的指針，下標為 1 的位置存儲指向子節點 b 的指針，以此類推，下標為 25 的位置，存儲的是指向的子節點 z 的指針。如果某個字符的子節點不存在，我們就在對應的下標的位置存儲 null。

class TrieNode {char data;TrieNode children[26]; }

當我們在 Trie 樹中查找字符串的時候，我們就可以通過字符的 ASCII 碼減去“a”的 ASCII 碼，迅速找到匹配的子節點的指針。比如，d 的 ASCII 碼減去 a 的 ASCII 碼就是 3，那子節點 d 的指針就存儲在數組中下標為 3 的位置中。

描述了這么多，有可能你還是有點懵，我把上面的描述翻譯成了代碼，你可以結合著一塊看下，應該有助于你理解。

public class Trie {private TrieNode root = new TrieNode('/'); // 存儲無意義字符// 往 Trie 樹中插入一個字符串public void insert(char[] text) {TrieNode p = root;for (int i = 0; i < text.length; ++i) {int index = text[i] - 'a';if (p.children[index] == null) {TrieNode newNode = new TrieNode(text[i]);p.children[index] = newNode;}p = p.children[index];}p.isEndingChar = true;}// 在 Trie 樹中查找一個字符串public boolean find(char[] pattern) {TrieNode p = root;for (int i = 0; i < pattern.length; ++i) {int index = pattern[i] - 'a';if (p.children[index] == null) {return false; // 不存在 pattern}p = p.children[index];}if (p.isEndingChar == false) return false; // 不能完全匹配，只是前綴else return true; // 找到 pattern}public class TrieNode {public char data;public TrieNode[] children = new TrieNode[26];public boolean isEndingChar = false;public TrieNode(char data) {this.data = data;}} }

Trie 樹的實現，你現在應該搞懂了。現在，我們來看下，在 Trie 樹中，查找某個字符串的時間復雜度是多少？

如果要在一組字符串中，頻繁地查詢某些字符串，用 Trie 樹會非常高效。構建 Trie 樹的過程，需要掃描所有的字符串，時間復雜度是 O(n)（n 表示所有字符串的長度和）。但是一旦構建成功之后，后續的查詢操作會非常高效。

每次查詢時，如果要查詢的字符串長度是 k，那我們只需要比對大約 k 個節點，就能完成查詢操作。跟原本那組字符串的長度和個數沒有任何關系。所以說，構建好 Trie 樹后，在其中查找字符串的時間復雜度是 O(k)，k 表示要查找的字符串的長度。

Trie 樹真的很耗內存嗎？

前面我們講了 Trie 樹的實現，也分析了時間復雜度。現在你應該知道，Trie 樹是一種非常獨特的、高效的字符串匹配方法。但是，關于 Trie 樹，你有沒有聽過這樣一種說法：“Trie 樹是非常耗內存的，用的是一種空間換時間的思路”。這是什么原因呢？

剛剛我們在講 Trie 樹的實現的時候，講到用數組來存儲一個節點的子節點的指針。如果字符串中包含從 a 到 z 這 26 個字符，那每個節點都要存儲一個長度為 26 的數組，并且每個數組存儲一個 8 字節指針（或者是 4 字節，這個大小跟 CPU、操作系統、編譯器等有關）。而且，即便一個節點只有很少的子節點，遠小于 26 個，比如 3、4 個，我們也要維護一個長度為 26 的數組。

我們前面講過，Trie 樹的本質是避免重復存儲一組字符串的相同前綴子串，但是現在每個字符（對應一個節點）的存儲遠遠大于 1 個字節。按照我們上面舉的例子，數組長度為 26，每個元素是 8 字節，那每個節點就會額外需要 26*8=208 個字節。而且這還是只包含 26 個字符的情況。

如果字符串中不僅包含小寫字母，還包含大寫字母、數字、甚至是中文，那需要的存儲空間就更多了。所以，也就是說，在某些情況下，Trie 樹不一定會節省存儲空間。在重復的前綴并不多的情況下，Trie 樹不但不能節省內存，還有可能會浪費更多的內存。

當然，我們不可否認，Trie 樹盡管有可能很浪費內存，但是確實非常高效。那為了解決這個內存問題，我們是否有其他辦法呢？

我們可以稍微犧牲一點查詢的效率，將每個節點中的數組換成其他數據結構，來存儲一個節點的子節點指針。用哪種數據結構呢？我們的選擇其實有很多，比如有序數組、跳表、散列表、紅黑樹等。

假設我們用有序數組，數組中的指針按照所指向的子節點中的字符的大小順序排列。查詢的時候，我們可以通過二分查找的方法，快速查找到某個字符應該匹配的子節點的指針。但是，在往 Trie 樹中插入一個字符串的時候，我們為了維護數組中數據的有序性，就會稍微慢了點。

替換成其他數據結構的思路是類似的，這里我就不一一分析了，你可以結合前面學過的內容，自己分析一下。

實際上，Trie 樹的變體有很多，都可以在一定程度上解決內存消耗的問題。比如，縮點優化，就是對只有一個子節點的節點，而且此節點不是一個串的結束節點，可以將此節點與子節點合并。這樣可以節省空間，但卻增加了編碼難度。這里我就不展開詳細講解了，你如果感興趣，可以自行研究下。

Trie 樹與散列表、紅黑樹的比較

實際上，字符串的匹配問題，籠統上講，其實就是數據的查找問題。對于支持動態數據高效操作的數據結構，我們前面已經講過好多了，比如散列表、紅黑樹、跳表等等。實際上，這些數據結構也可以實現在一組字符串中查找字符串的功能。我們選了兩種數據結構，散列表和紅黑樹，跟 Trie 樹比較一下，看看它們各自的優缺點和應用場景。

在剛剛講的這個場景，在一組字符串中查找字符串，Trie 樹實際上表現得并不好。它對要處理的字符串有及其嚴苛的要求。

第一，字符串中包含的字符集不能太大。我們前面講到，如果字符集太大，那存儲空間可能就會浪費很多。即便可以優化，但也要付出犧牲查詢、插入效率的代價。

第二，要求字符串的前綴重合比較多，不然空間消耗會變大很多。

第三，如果要用 Trie 樹解決問題，那我們就要自己從零開始實現一個 Trie 樹，還要保證沒有 bug，這個在工程上是將簡單問題復雜化，除非必須，一般不建議這樣做。

第四，我們知道，通過指針串起來的數據塊是不連續的，而 Trie 樹中用到了指針，所以，對緩存并不友好，性能上會打個折扣。

綜合這幾點，針對在一組字符串中查找字符串的問題，我們在工程中，更傾向于用散列表或者紅黑樹。因為這兩種數據結構，我們都不需要自己去實現，直接利用編程語言中提供的現成類庫就行了。

講到這里，你可能要疑惑了，講了半天，我對 Trie 樹一通否定，還讓你用紅黑樹或者散列表，那 Trie 樹是不是就沒用了呢？是不是今天的內容就白學了呢？

實際上，Trie 樹只是不適合精確匹配查找，這種問題更適合用散列表或者紅黑樹來解決。Trie 樹比較適合的是查找前綴匹配的字符串，也就是類似開篇問題的那種場景。

實際上，Trie 樹的這個應用可以擴展到更加廣泛的一個應用上，就是自動輸入補全，比如輸入法自動補全功能、IDE 代碼編輯器自動補全功能、瀏覽器網址輸入的自動補全功能等等。

Trie 樹是一種解決字符串快速匹配問題的數據結構。如果用來構建 Trie 樹的這一組字符串中，前綴重復的情況不是很多，那 Trie 樹這種數據結構總體上來講是比較費內存的，是一種空間換時間的解決問題思路。

盡管比較耗費內存，但是對內存不敏感或者內存消耗在接受范圍內的情況下，在 Trie 樹中做字符串匹配還是非常高效的，時間復雜度是 O(k)，k 表示要匹配的字符串的長度。

但是，Trie 樹的優勢并不在于，用它來做動態集合數據的查找，因為，這個工作完全可以用更加合適的散列表或者紅黑樹來替代。Trie 樹最有優勢的是查找前綴匹配的字符串，比如搜索引擎中的關鍵詞提示功能這個場景，就比較適合用它來解決，也是 Trie 樹比較經典的應用場景。

擴展閱讀：Trie樹的開源庫：Apache Commons、DAT（雙數組trie樹）、后綴樹

AC自動機

很多支持用戶發表文本內容的網站，比如 BBS，大都會有敏感詞過濾功能，用來過濾掉用戶輸入的一些淫穢、反動、謾罵等內容。你有沒有想過，這個功能是怎么實現的呢？

實際上，這些功能最基本的原理就是字符串匹配算法，也就是通過維護一個敏感詞的字典，當用戶輸入一段文字內容之后，通過字符串匹配算法，來查找用戶輸入的這段文字，是否包含敏感詞。如果有，就用“***”把它替代掉。

我們前面講過好幾種字符串匹配算法了，它們都可以處理這個問題。但是，對于訪問量巨大的網站來說，比如淘寶，用戶每天的評論數有幾億、甚至幾十億。這時候，我們對敏感詞過濾系統的性能要求就要很高。畢竟，我們也不想，用戶輸入內容之后，要等幾秒才能發送出去吧？我們也不想，為了這個功能耗費過多的機器吧？那如何才能實現一個高性能的敏感詞過濾系統呢？這就要用到今天的多模式串匹配算法。

基于單模式串和 Trie 樹實現的敏感詞過濾

我們前面幾節講了好幾種字符串匹配算法，有 BF 算法、RK 算法、BM 算法、KMP 算法，還有 Trie 樹。前面四種算法都是單模式串匹配算法，只有 Trie 樹是多模式串匹配算法。

我說過，單模式串匹配算法，是在一個模式串和一個主串之間進行匹配，也就是說，在一個主串中查找一個模式串。多模式串匹配算法，就是在多個模式串和一個主串之間做匹配，也就是說，在一個主串中查找多個模式串。

盡管，單模式串匹配算法也能完成多模式串的匹配工作。例如開篇的思考題，我們可以針對每個敏感詞，通過單模式串匹配算法（比如 KMP 算法）與用戶輸入的文字內容進行匹配。但是，這樣做的話，每個匹配過程都需要掃描一遍用戶輸入的內容。整個過程下來就要掃描很多遍用戶輸入的內容。如果敏感詞很多，比如幾千個，并且用戶輸入的內容很長，假如有上千個字符，那我們就需要掃描幾千遍這樣的輸入內容。很顯然，這種處理思路比較低效。

與單模式匹配算法相比，多模式匹配算法在這個問題的處理上就很高效了。它只需要掃描一遍主串，就能在主串中一次性查找多個模式串是否存在，從而大大提高匹配效率。我們知道，Trie 樹就是一種多模式串匹配算法。那如何用 Trie 樹實現敏感詞過濾功能呢？

我們可以對敏感詞字典進行預處理，構建成 Trie 樹結構。這個預處理的操作只需要做一次，如果敏感詞字典動態更新了，比如刪除、添加了一個敏感詞，那我們只需要動態更新一下 Trie 樹就可以了。

當用戶輸入一個文本內容后，我們把用戶輸入的內容作為主串，從第一個字符（假設是字符 C）開始，在 Trie 樹中匹配。當匹配到 Trie 樹的葉子節點，或者中途遇到不匹配字符的時候，我們將主串的開始匹配位置后移一位，也就是從字符 C 的下一個字符開始，重新在 Trie 樹中匹配。

基于 Trie 樹的這種處理方法，有點類似單模式串匹配的 BF 算法。我們知道，單模式串匹配算法中，KMP 算法對 BF 算法進行改進，引入了 next 數組，讓匹配失敗時，盡可能將模式串往后多滑動幾位。借鑒單模式串的優化改進方法，能否對多模式串 Trie 樹進行改進，進一步提高 Trie 樹的效率呢？這就要用到 AC 自動機算法了。

經典的多模式串匹配算法：AC 自動機

AC 自動機算法，全稱是 Aho-Corasick 算法。其實，Trie 樹跟 AC 自動機之間的關系，就像單串匹配中樸素的串匹配算法，跟 KMP 算法之間的關系一樣，只不過前者針對的是多模式串而已。所以，AC 自動機實際上就是在 Trie 樹之上，加了類似 KMP 的 next 數組，只不過此處的 next 數組是構建在樹上罷了。如果代碼表示，就是下面這個樣子：

public class AcNode {public char data; public AcNode[] children = new AcNode[26]; // 字符集只包含 a~z 這 26 個字符public boolean isEndingChar = false; // 結尾字符為 truepublic int length = -1; // 當 isEndingChar=true 時，記錄模式串長度public AcNode fail; // 失敗指針public AcNode(char data) {this.data = data;} }

所以，AC 自動機的構建，包含兩個操作：

• 將多個模式串構建成 Trie 樹；
• 在 Trie 樹上構建失敗指針（相當于 KMP 中的失效函數 next 數組）。

關于如何構建 Trie 樹，我們上一節已經講過了。所以，這里我們就重點看下，構建好 Trie 樹之后，如何在它之上構建失敗指針？

我用一個例子給你講解。這里有 4 個模式串，分別是 c，bc，bcd，abcd；主串是 abcd。

Trie 樹中的每一個節點都有一個失敗指針，它的作用和構建過程，跟 KMP 算法中的 next 數組極其相似。所以要想看懂這節內容，你要先理解 KMP 算法中 next 數組的構建過程。如果你還有點不清楚，建議你先回頭去弄懂 KMP 算法。

假設我們沿 Trie 樹走到 p 節點，也就是下圖中的紫色節點，那 p 的失敗指針就是從 root 走到紫色節點形成的字符串 abc，跟所有模式串前綴匹配的最長可匹配后綴子串，就是箭頭指的 bc 模式串。

這里的最長可匹配后綴子串，我稍微解釋一下。字符串 abc 的后綴子串有兩個 bc，c，我們拿它們與其他模式串匹配，如果某個后綴子串可以匹配某個模式串的前綴，那我們就把這個后綴子串叫作可匹配后綴子串。

我們從可匹配后綴子串中，找出最長的一個，就是剛剛講到的最長可匹配后綴子串。我們將 p 節點的失敗指針指向那個最長匹配后綴子串對應的模式串的前綴的最后一個節點，就是下圖中箭頭指向的節點。

計算每個節點的失敗指針這個過程看起來有些復雜。其實，如果我們把樹中相同深度的節點放到同一層，那么某個節點的失敗指針只有可能出現在它所在層的上一層。

我們可以像 KMP 算法那樣，當我們要求某個節點的失敗指針的時候，我們通過已經求得的、深度更小的那些節點的失敗指針來推導。也就是說，我們可以逐層依次來求解每個節點的失敗指針。所以，失敗指針的構建過程，是一個按層遍歷樹的過程。

首先 root 的失敗指針為 NULL，也就是指向自己。當我們已經求得某個節點 p 的失敗指針之后，如何尋找它的子節點的失敗指針呢？

我們假設節點 p 的失敗指針指向節點 q，我們看節點 p 的子節點 pc 對應的字符，是否也可以在節點 q 的子節點中找到。如果找到了節點 q 的一個子節點 qc，對應的字符跟節點 pc 對應的字符相同，則將節點 pc 的失敗指針指向節點 qc。

如果節點 q 中沒有子節點的字符等于節點 pc 包含的字符，則令 q=q->fail（fail 表示失敗指針，這里有沒有很像 KMP 算法里求 next 的過程？），繼續上面的查找，直到 q 是 root 為止，如果還沒有找到相同字符的子節點，就讓節點 pc 的失敗指針指向 root。

我將構建失敗指針的代碼貼在這里，你可以對照著講解一塊看下，應該更容易理解。這里面，構建 Trie 樹的代碼我并沒有貼出來，你可以參看上一節的代碼，自己實現。

public void buildFailurePointer() {Queue<AcNode> queue = new LinkedList<>();root.fail = null;queue.add(root);while (!queue.isEmpty()) {AcNode p = queue.remove();for (int i = 0; i < 26; ++i) {AcNode pc = p.children[i];if (pc == null) continue;if (p == root) {pc.fail = root;} else {AcNode q = p.fail;while (q != null) {AcNode qc = q.children[pc.data - 'a'];if (qc != null) {pc.fail = qc;break;}q = q.fail;}if (q == null) {pc.fail = root;}}queue.add(pc);}} }

通過按層來計算每個節點的子節點的失效指針，剛剛舉的那個例子，最后構建完成之后的 AC 自動機就是下面這個樣子：

AC 自動機到此就構建完成了。我們現在來看下，如何在 AC 自動機上匹配主串？

我們還是拿之前的例子來講解。在匹配過程中，主串從 i=0 開始，AC 自動機從指針 p=root 開始，假設模式串是 b，主串是 a。

• 如果 p 指向的節點有一個等于 b[i] 的子節點 x，我們就更新 p 指向 x，這個時候我們需要通過失敗指針，檢測一系列失敗指針為結尾的路徑是否是模式串。這一句不好理解，你可以結合代碼看。處理完之后，我們將 i 加一，繼續這兩個過程；
• 如果 p 指向的節點沒有等于 b[i] 的子節點，那失敗指針就派上用場了，我們讓 p=p->fail，然后繼續這 2 個過程。

關于匹配的這部分，文字描述不如代碼看得清楚，所以我把代碼貼了出來，非常簡短，并且添加了詳細的注釋，你可以對照著看下。這段代碼輸出的就是，在主串中每個可以匹配的模式串出現的位置。

public void match(char[] text) { // text 是主串int n = text.length;AcNode p = root;for (int i = 0; i < n; ++i) {int idx = text[i] - 'a';while (p.children[idx] == null && p != root) {p = p.fail; // 失敗指針發揮作用的地方}p = p.children[idx];if (p == null) p = root; // 如果沒有匹配的，從 root 開始重新匹配AcNode tmp = p;while (tmp != root) { // 打印出可以匹配的模式串if (tmp.isEndingChar == true) {int pos = i-tmp.length+1;System.out.println(" 匹配起始下標 " + pos + "; 長度 " + tmp.length);}tmp = tmp.fail;}} }

解答開篇

AC 自動機的內容講完了，關于開篇的問題，你應該能解答了吧？實際上，我上面貼出來的代碼，已經是一個敏感詞過濾的原型代碼了。它可以找到所有敏感詞出現的位置（在用戶輸入的文本中的起始下標）。你只需要稍加改造，再遍歷一遍文本內容（主串），就可以將文本中的所有敏感詞替換成“***”。

所以我這里著重講一下，AC 自動機實現的敏感詞過濾系統，是否比單模式串匹配方法更高效呢？

首先，我們需要將敏感詞構建成 AC 自動機，包括構建 Trie 樹以及構建失敗指針。

我們上一節講過，Trie 樹構建的時間復雜度是 O(m*len)，其中 len 表示敏感詞的平均長度，m 表示敏感詞的個數。那構建失敗指針的時間復雜度是多少呢？我這里給出一個不是很緊確的上界。

假設 Trie 樹中總的節點個數是 k，每個節點構建失敗指針的時候，（你可以看下代碼）最耗時的環節是 while 循環中的 q=q->fail，每運行一次這個語句，q 指向節點的深度都會減少 1，而樹的高度最高也不會超過 len，所以每個節點構建失敗指針的時間復雜度是 O(len)。整個失敗指針的構建過程就是 O(k*len)。

不過，AC 自動機的構建過程都是預先處理好的，構建好之后，并不會頻繁地更新，所以不會影響到敏感詞過濾的運行效率。

我們再來看下，用 AC 自動機做匹配的時間復雜度是多少？

跟剛剛構建失敗指針的分析類似，for 循環依次遍歷主串中的每個字符，for 循環內部最耗時的部分也是 while 循環，而這一部分的時間復雜度也是 O(len)，所以總的匹配的時間復雜度就是 O(n*len)。因為敏感詞并不會很長，而且這個時間復雜度只是一個非常寬泛的上限，實際情況下，可能近似于 O(n)，所以 AC 自動機做敏感詞過濾，性能非常高。

你可以會說，從時間復雜度上看，AC 自動機匹配的效率跟 Trie 樹一樣啊。實際上，因為失效指針可能大部分情況下都指向 root 節點，所以絕大部分情況下，在 AC 自動機上做匹配的效率要遠高于剛剛計算出的比較寬泛的時間復雜度。只有在極端情況下，如圖所示，AC 自動機的性能才會退化的跟 Trie 樹一樣。

多模式串匹配算法，AC 自動機。單模式串匹配算法是為了快速在主串中查找一個模式串，而多模式串匹配算法是為了快速在主串中查找多個模式串。

AC 自動機是基于 Trie 樹的一種改進算法，它跟 Trie 樹的關系，就像單模式串中，KMP 算法與 BF 算法的關系一樣。KMP 算法中有一個非常關鍵的 next 數組，類比到 AC 自動機中就是失敗指針。而且，AC 自動機失敗指針的構建過程，跟 KMP 算法中計算 next 數組極其相似。所以，要理解 AC 自動機，最好先掌握 KMP 算法，因為 AC 自動機其實就是 KMP 算法在多模式串上的改造。

整個 AC 自動機算法包含兩個部分，第一部分是將多個模式串構建成 AC 自動機，第二部分是在 AC 自動機中匹配主串。第一部分又分為兩個小的步驟，一個是將模式串構建成 Trie 樹，另一個是在 Trie 樹上構建失敗指針。

總結

以上是生活随笔為你收集整理的数据结构与算法之美笔记——基础篇（下）：图、字符串匹配算法（BF 算法和 RK 算法、BM 算法和 KMP 算法 、Trie 树和 AC 自动机）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。