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