字符串匹配算法，即在一個字符串中查找另個字符串的位置。如果在字符串A中查找字符串B是否存在，那么字符串A稱為主串，字符串B稱為模式串。主串長度為m，模式串長度為n。

字符串匹配

BF (Brute Force) 暴力匹配算法

充主串A的起始位0開始，檢查長度n的子串，是否和模式串相等。如果不相等，將主串的指針往后挪一位，從主串的1，2，3 ... m-n位開始，依次檢查長度為n的子串，是否和模式串匹配。

BF算法

時間復雜度為 O(m*n)，但是實際的效率比理論值效率高一些。

RK（Rabin-Karp）算法

和BF算法思想一致，只是在比較A的子串與模式串是否匹配時，使用Hash算法比較hash后的數值，而不是一一比較字符。

RK算法

其中的Hash算法比較講究，好的Hash算法可以大大提高效率，而查的Hash算法，可能使得算法效率還比不上BF。
如果字符串只有小寫字符，可將字符串作為26進制的數來看待。同時緩存26^n,26(n-1) 等預處理的值，可以提高計算速度。

BM（Boyer-Moore）算法

非常高效的算法，據說是KMP算法的3-4倍。算法思路上與BF一致，只是每次往后挪的位數多一些。而且在比較子串與模式串時，是從最后一個字符開始，往前比較。

• 壞字符規(guī)則（bad character rule）
• 好后綴規(guī)則（good suffix rule）

壞字符規(guī)則

從后往前，依次比較主串和模式串的字符，出現不相等的字符時，主串中的那個就是“壞字符”。
如果模式串中有壞字符，將模式串往后移動讓兩個字符對齊。如果模式串中沒有壞字符，直接將模式串移到壞字符后面。

BM算法

好后綴規(guī)則

主串和模式串從后往前，相同的部分稱為“好后綴”。

• 模式串中有好后綴，可以后移模式串，讓二者對齊。

  
  
  好后綴規(guī)則1

• 好后綴的后面的子串和模式串前綴子串相同，移動模式串到相應的位置。

  
  
  好后綴規(guī)則2

• 其他情況，將模式串挪到好后綴后面。

預處理

要想高效實用這兩個規(guī)則，需要對模式串進行預處理。

壞字符預處理

將模式串的字符位置放到哈希表，在以便快速查找壞字符。
hash[key] = value;

• key - 模式串的字符
• value - 字符在模式串中的位置。
  相同的字符，取最后一個位置。

好后綴預處理

1. 處理模式串中后綴子串，檢查在模式串中其他位置是否有形同的的子串，使用 int[] A 數組來存儲。
   A[i] = j;
   表示從后往前 i+1 長度的字符串，在模式串中存在，位置是 j。

2. 處理模式串的后綴子串，是否與模式串的前綴子串匹配。同樣適用 bool[] B 數組來存儲。
   B[i] = true/false;
   表示從后往前 i+1 長度的字符串，true表示和前綴子串匹配，false表示不匹配。

代碼實現思路如下圖，j從 0 -> n-1 遍歷，對于每個j，相應的k指向末尾，同時往前移動，如果指向的字符不同，馬上停止。得到值存入A。如果j指針能走到0，那B中設置為true。

好后綴預處理算法