單模和多模的區別在於，妳是否能通過壹次遍歷主串找出多模的所有串。
英文全稱是Brute Force，暴力匹配算法，匹配字符串的方法暴力易懂。總的想法是:
我們可以看到，在極端情況下，如果在主字符串aaaa中搜索模式字符串aab...aab，那麽總* * *需要搜索(n-m+1)次，每次都需要比較m次，那麽時間復雜度就為(n-m+1)*m，也就是O (n * m)。但實際上也不會那麽低效，因為我們使用場景中的主串和模式串都不會太長，而且在比較每個子串和模式串的時候，只要中間有壹個不匹配，當前的比較就會提前結束，所以大多數情況下時間復雜度會優於O(n*m)。
我們在BF算法的基礎上引入了hash算法。我們不需要將每個子串與模式串逐字符進行比較，而是計算每個子串的哈希值，然後與模式串的哈希值進行比較。如果相等，說明有壹個子串與模式串匹配。
雖然我們只需要比較模式串和子串的hash值就可以得到匹配結果，次數是(n-m+1)，但是對每個子串進行hash計算時，需要遍歷每個字符，所以次數也是m，所以總的時間復雜度仍然是O(n*m)，沒有得到明顯的提高。
那麽如何才能想出壹個辦法來提高每個子串哈希值的計算時間呢？這就是RK算法的精髓。假設子串所包含的字符集中的元素個數為K，那麽子串就用壹個K進制數來表示，然後哈希的過程就是把K進制數轉換成十進制數，這個十進制數就是子串的哈希值。
相鄰子字符串的哈希值是定期計算的。我們只需要遍歷壹次主串就可以得到所有子串的哈希值，算法復雜度為O(n)，而不是原來每個子串的時間復雜度為O(m)。
然後將模式字符串的哈希值與所有子字符串的哈希值進行比較。每次比較的時間復雜度為O(1)，總比較次數為* * * (n-m+1)，所以RK算法的總時間開銷為O(n)+O (1) * O (n-m)。
當然，哪裏有哈希，哪裏就可能有哈希沖突。有可能子串和哈希值與模式串的哈希值相同，但內容不同。這時候我該怎麽辦？其實很簡單。對於哈希值相同的子串，可以加雙保險，比較這M個字符是否都壹樣。總時間成本為O(n)+O(1)* O(n-m+1)+O(m)，也就是O(n)。
極端情況下有很多哈希沖突怎麽辦？我們需要逐個比較每個與模式串具有相同哈希值的子串，所以總的時間開銷會是O(n)+O(1)* O(n-m+1)+O(m)* O(n-m+1)，也就是O (n *)
在真實文本編輯器中搜索和替換字符串時，使用的算法既不是BF算法，也不是RK算法。BF算法只適用於不是很長的主串，而RK算法需要設計壹個碰撞概率低的hash算法，難度比較大，所以實際上用的是BM算法，這是工程上很常見的字符串匹配算法，效率最高。
算法的思路和流程有些復雜，後面會整理。
KMP算法本質上與BM算法相同。算法的思路和流程有些復雜，後面會整理。
瀏覽器輸入框中的智能輸入匹配是如何實現的，它是如何做動態字符串匹配搜索的？這使用了Trie樹。
字典樹(Dictionary tree)又稱字典樹，是專門用來快速查找字符串前綴匹配結果的樹結構。其本質是將所有字符串的重復前綴組合起來構造壹棵多分支樹。
其中，根節點不包含任何信息，每個節點代表壹個字符，從根節點到紅色節點的路徑代表壹個存儲的字符串。當我們在上面的Trie樹中尋找“他”時，發現“他”並不是壹個字符串，而是“妳好”和“她”的公共前綴，那麽我們就會找到這兩個字符串返回。
樹是如何存儲在內存中的？因為每個節點可能包含所有字符，所以每個節點都是壹個數組(或哈希表),用於存儲指向每個字符及其後綴節點的指針。
使用Trie樹，在構造之初，時間復雜度為O(n)，其中n為所有字符串長度之和，但壹旦構造完成，頻繁查詢壹個字符串效率很高，時間復雜度為O(k)，其中k為搜索字符串的長度。
Trie樹雖然查詢效率高，但是浪費內存。每個節點都必須維護壹個數組來存儲所有可能的字符數據和指向下壹個節點的指針，所以當所有字符串的公共前綴不多的時候，內存空間的浪費就更大了。其實這個問題也有相應的解決方法。我們可以不用數組，而是用有序數組，哈希表，紅黑樹來存儲，這樣可以相應降低性能，節省內存空間。
Trie樹不僅可以實現在瀏覽器中動態輸入內容搜索候選項的功能，還可以實現多模式敏感詞匹配的功能。假設我們需要檢查用戶輸入的敏感詞，將所有敏感內容替換為* * *，那麽如何實現呢？
首先，我們可以維護壹個敏感詞詞典，使用上述四種單壹模式匹配算法也可以實現，但是對用戶輸入的內容進行n次遍歷，效率非常低，其中n是所有敏感詞的模式串。但如果我們將敏感詞詞典維護為Trie樹，然後在Trie樹中從位置0開始查詢用戶的輸入，如果匹配到紅色節點，則說明有敏感詞；如果沒有匹配到紅色節點，我們將從用戶輸入內容的下壹個位置開始在Trie樹中繼續查詢，直到遍歷完用戶的輸入內容，所以我們只遍歷壹次主字符串。
然而，更有效的多模式字符串匹配使用下面的AC自動機。
如果把Trie樹比作BF算法，KMP算法是BF算法的改進，那麽AC自動機也是用同樣的思路改進Trie樹的。
算法的思路和流程有些復雜，後面會整理。