BF算法
BF算法中的BF是brute force的縮寫囊咏，中文叫做暴力匹配算法，也加樸素匹配算法塔橡。算法特點(diǎn)：“暴力” 梅割、簡(jiǎn)單、好懂葛家、性能不佳户辞。
引入兩個(gè)概念：主串與模式串。
比方說(shuō)：我們?cè)谧址瓵中查找字符串B癞谒，那么字符串A就是主串底燎，字符串B就是模式串。
我們把主串的長(zhǎng)度記作n,模式串的長(zhǎng)度記作m弹砚。因?yàn)槲覀兪窃谥鞔胁檎夷Ｊ酱轵剑詎>m。
BF算法的思想：我們?cè)谥鞔醒刚ぃ瑱z查起始位置分別是0殊校、1、2读存、3为流、...n-m且長(zhǎng)度為m的n-m+1個(gè)子串，看有沒有跟模式串匹配的让簿。
圖例：
這種算法的最壞時(shí)間復(fù)雜度為O(n*m)敬察。
盡管理論上，BF算法的時(shí)間復(fù)雜度很高尔当，是O(n*m)莲祸。 但在實(shí)際開發(fā)中它是一個(gè)比較常用的字符串匹配算法。為什么這么說(shuō)呢椭迎？原因有兩點(diǎn)锐帜。
- 第一：實(shí)際的軟件開發(fā)中，大部分情況下畜号，模式串與主串的長(zhǎng)度都不會(huì)太長(zhǎng)缴阎。
- 第二：BF算法的思想簡(jiǎn)單，代碼實(shí)現(xiàn)也非常簡(jiǎn)單简软。簡(jiǎn)單意味著不容易出錯(cuò)蛮拔，如果有bug也容易暴露和修復(fù)述暂。
RK算法
RK算法的全稱叫Rabin-Karp算法，是由它的兩位發(fā)明者Rabin與Karp的名字來(lái)命名建炫。
RK算法的思想是這樣的：我們通過哈希算法對(duì)主串中的n-m+1個(gè)子串分別求哈希值畦韭，然后逐個(gè)與模式串的哈希值比較大小。如果某個(gè)子串的哈希值與模式串相等肛跌，那就說(shuō)明對(duì)應(yīng)的子串與模式串匹配了（這里不考慮哈希沖突）艺配。有哈希沖突怎么辦，解決方法也很簡(jiǎn)單（當(dāng)我們發(fā)現(xiàn)子串的哈希值與模式串相等時(shí)惋砂，再對(duì)比一下子串與模式串就可以了）。哈希值是數(shù)值绳锅，數(shù)值之間的比較是比較快速的西饵。
