APP
BF算法
bf算法(brute force)顧名思義，是很暴力，很樸素的算法，我們把想要匹配的字符串叫做模式串，通俗理解來說就是模板，把被進行搜索來查找有無匹配的子串的字符串叫做主串，比如用戶輸入的字符串。
bf算法是這樣的：假設主串長度為n，模式串的長度對我們從主串的初始位置0開始，每次查找長度為m的字符串，直到找到匹配的字符串或者最多查找了n - m + 1次結束。
為什么說最多只會查找n - m + 1呢？從圖中就能看出來了，當比較到了n - m次時，這時主串中還沒有被比較過的字符就只剩下m個了，你頂多只能再比較一次，所以最多只能是n - m + 1次。
?
bf算法在極端情況下，比如，主串是一大串a(chǎn)，而子串是aaab，那么每次比較m個字符，比較n - m + 1次，會有時間復雜度O(n * m)，這看起來很高，但是事實上，我們可以每次比較時一旦遇到不匹配的字符就停下當次比較，而且實際開發(fā)遇到的主串和模式串一般不會很長，所以其實大部分情況下，執(zhí)行效率都會比這個O(n * m)高很多，并且bf算法暴力樸素，不容易出錯，即便有出錯也更容易排查出來，在工程中，滿足性能的情況下，簡單是首選，這也是KISS設計原則(keep it simple and stupid)所以，bf算法還是很常用的。
?
RK算法（Rabin - Karp）
rk算法以它的兩位發(fā)明者進行命名，該算法其實是在暴力匹配算法的基礎上配合哈希算法使用。
為什么要配合上哈希算法使用呢，這是因為暴力匹配算法時間復雜度并不是很低，所以我們將主串的每個子串先轉(zhuǎn)為哈希值（注意要考慮哈希值沖突，但我們這個例子中的哈希算法，對于不同字符串，哈希值是不同的，沒有沖突），然后把模式串的哈希值與各個子串比較，如果相等，就證明匹配成功。并且由于哈希值是數(shù)字，所以比較會很迅速。
?
當然啦，這樣的話匹配算法的復雜度不僅受哈希值比較影響，還會受哈希函數(shù)把字符串轉(zhuǎn)化為哈希值的計算速度的影響，所以我們還要選擇合適的哈希函數(shù)。
?
假設我們要操作的字符串集含有K個字符，那么我們可以用K進制來代替字符串。
?
比如我們可以假設我們操作的字符集只含有a~z26個字母，那么我們就可以用26進制，a對應1，b對應2.....這樣對應下去，這時由于進制達到了兩位數(shù)，所以將子串轉(zhuǎn)化成十進制數(shù)，這個十進制數(shù)來當哈希值就可以了。轉(zhuǎn)化的方式還是“乘權求和”。
?
并且你會發(fā)現(xiàn)，子串與子串之間的哈希值是大部分都重疊的，對于S[i - 1]和S[i]兩個相鄰子串來說，S[i]的哈希值按權展開的形式是S[i] 的按權展開的基礎上，去掉最大的，然后整體乘基數(shù)的一次方，再加上S[i]的最后一個字符的下一個字符的值。
?
?
所以我們可以得出每個子串的的哈希值公式。
?
?
而且，還要注意，基數(shù)的各個次冪被反復使用且不被更改，所以我們提早算好，然后儲存在一個數(shù)組中，當需要的時候，直接按下標讀取就可以了，節(jié)省了很多時間。要是我們需要自己設置26個字母的值，26個字母對應的值也可以這樣處理。
?
?
如果就看上面的例子，RK算法的時間復雜度包含了遍歷字符串計算子串哈希值和比較所有子串和模式串，也就是O（n） + O（n） == O（2n）== O（n）。
?
但是，我們還要注意，哈希值是用整數(shù)存儲的，所以有可能出現(xiàn)數(shù)值溢出，那么我們可以把字符串的每個字母全部加起來，加起來的值來當哈希值，這樣溢出的概率就小得多了，當然，這會造成哈希沖突，所以我們這時的比較，當哈希值相同后，還要再比較以便子串和模式串本身，才能判斷相不相同，極端情況下，會每一次都要在比較本身，也就是退化回了暴力匹配算法的時間復雜度，不過這也不多見，總體上，RK算法還是比BF算法效率高。
而且這是一種最簡單的設計方法而已，還有許多的優(yōu)化方法可以使哈希沖突概率更小，比如將每一個字母從小到大對應一個素數(shù)。
本文摘自 ：https://www.cnblogs.com/
