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