演算法串聯接

⑴ 串的模式匹配演算法

本文主要講述了串的模式匹配演算法，包括BF演算法、RK演算法、KMP演算法、BM演算法，使用不同的演算法實現目標串查找子串，重點在於分析的過程，通過不同的演算法分析提高邏輯思維能力

模式匹配的目的就是在目標串中查找與模式串相等的子串。在這里稱呼主串為s，模式串為t，主串的長度為n，模式串的長度為m

暴力演算法，將目標串和模式串的每個字元都進行一一比較。性能最差，但是使用最廣，因為實現簡單，而且在字元串較小的情況下耗費的性能也很小。

O(n*m)

RK演算法把字元串比較問題，轉換為了Hash值比較問題。
將模式串t的每個字元的比較改成了將串作為整體與目標串進行哈希值比較，這樣就減少了比較次數
以前模式串與子串的比較需要比較每個字元，現在只要整體比較依次哈希值就可以。所以減少了比較次數。

哈希演算法

這里我們可以發現一個Hash沖突問題，比如"abc"和"bc"的Hash值是一樣的，因為最高位是0。所以還需要進行哈希沖突演算法。

哈希沖突演算法：

利用前一個結果計算下一個哈希值
這是因為目標串的相鄰子串，其實相差的只有第一個字元和最後一個字元，其他字元是相同的，
所以我們可以利用前一個計算結果減去前一個字元串的第一個字元串，加上這個字元串的最後一個字元就夠了。

針對BF的弊端，在KMP演算法中可以進行多字元的跳躍對比，以此來避免目標串的不必要回溯。

例子：

簡單說明一下：

真子串：

匹配：

例如：目標串："abxabcabcaby"，模式串："abcaby"

模式串的最大真子串為ab,
我們在匹配時，發現目標串的子串abcabc與模式串的前字元都匹配，最後一個字元不匹配
所以就從目標串的abcabc的後面abc開始與模式串進行匹配，而不需要匹配前面的abc了。

也就是從上一個a字元直接跳躍到了下一個a字元，而不是從b字元開始。

會存在一種情況：

實現思想：

它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP演算法的三四倍。BM演算法的原理很多復雜，比較難懂，學起來比較燒腦。
實現思想和KMP演算法基本上是一樣的，都是先計算模式串的真子串，之後再查找真子串的大小，當出現不匹配時，直接在真子串後進行匹配，區別於KMP演算法，它是從後往前匹配的

這里比上面的KMP演算法增加了一個壞字元規則，可以更快的跳躍，當然KMP演算法本身也可以使用壞字元規則

壞字元規則

好後綴規則