Boyer-Moore是一種快速的字符串匹配算法，它對(duì)目標(biāo)字符串（模式串）進(jìn)行倒序查找，并在字符串匹配失敗時(shí)無(wú)需像暴力查找那樣對(duì)整個(gè)模式串進(jìn)行重新匹配，而是通過壞字符和好后綴計(jì)算滑動(dòng)窗口，降低查詢的時(shí)間復(fù)雜度。
如圖：在 文本HERE IS A SIMPLE EXAMPLE中查找模式串EXAMPLE。Boyer-Moore算法（下文簡(jiǎn)稱B-M算法）從模式串的最后一個(gè)位置開始與文本進(jìn)行比較，模式串中的E與文本中的S不匹配，則稱字符S為壞字符。

1.png

由于在一開始比較的時(shí)候，模式串和文本頭部是對(duì)齊的。所以，此時(shí)文本的前7位字符不可能與模式串完全匹配，我們可以直接將模式串移動(dòng)7位到文本S的后一位。如下圖：

2.png

壞字符后移位數(shù)=壞字符在模式串中失配的位置-壞字符在模式串中上一次出現(xiàn)的位置
如果壞字符之前從未在模式串中出現(xiàn)，則位置默認(rèn)為-1。比如：在第一次比較時(shí)，字符S出現(xiàn)在模式串的第6位，而在E字符左側(cè)無(wú)字符S，即字符S從未在模式串中出現(xiàn)，則據(jù)計(jì)算規(guī)則得出模式串移動(dòng)位數(shù)=6-（-1）=7。在第二次比較時(shí)，字符S的上一次出現(xiàn)是在模式串的第四位，則后移位數(shù)=6-4=2。

3.png

在將模式串中的P后移2位對(duì)齊后得到上圖，此時(shí)從最后一位E開始比較：

4.png

• 模式串字符E與文本字符E匹配，繼續(xù)倒序比較

  
  
  5.png

• 模式串字符L與文本字符L匹配，繼續(xù)倒序比較

  
  
  6.png

• 模式串字符P與文本字符P匹配，繼續(xù)倒序比較

  
  
  8.png

• 模式串字符M與文本字符M匹配，繼續(xù)倒序比較

  
  
  9.png
• 模式串字符A與文本字符I不匹配，I為壞字符
  此時(shí)，得到I為壞字符，而前面匹配成功的MPLE，PLE,LE,E則被稱作好后綴。通過壞字符移位規(guī)則計(jì)算得到此時(shí)后移位數(shù)為2-（-1）=3位。那在這種部分字符有4位匹配的情況下，如果僅移動(dòng)3位，顯然移動(dòng)后很可能最后一位仍然不匹配，那還有更好的移位方法么？

在此次的匹配中，我們得到了4個(gè)好后綴，在壞字符移位不夠多的情況下，嘗試計(jì)算好后綴的移位結(jié)果，選取最優(yōu)解。好后綴的計(jì)算規(guī)則如下：

好后綴后移位數(shù)=好后綴的位置-好后綴在模式串中上一次出現(xiàn)時(shí)的位置
和壞字符類似，如果好后綴只出現(xiàn)一次，則其上一次出現(xiàn)位置為-1
好后綴的位置都指其最后一個(gè)字符在模式串中的位置
如有多個(gè)好后綴，則在計(jì)算時(shí)，除了最長(zhǎng)的那個(gè)好后綴，其他好后綴必須出現(xiàn)在模式串頭部中
以上文的好后綴MPLE,PLE,LE,E為例，接下來(lái)進(jìn)行其好后綴移位計(jì)算：

MPLE,未出現(xiàn)，上一次出現(xiàn)位置為-1
PLE,未出現(xiàn)在頭部，上一次出現(xiàn)位置為-1
LE,未出現(xiàn)在頭部，上一次出現(xiàn)位置為-1
E,出現(xiàn)在頭部，上一次出現(xiàn)位置為0
此處只能選取E進(jìn)行好后綴計(jì)算，得到后移位數(shù)=6-0= 6位。而此時(shí)壞字符后移位數(shù)位3位，顯然選用好后綴移位更多，此時(shí)選擇好后綴后移，移動(dòng)后，如下圖：

12.png

此時(shí)，P字符失配，根據(jù)壞字符規(guī)則6-4=2位，后移2位，移位后效果如下圖：

13.png