說(shuō)到Boyer-Moore算法，它是一個(gè)字符串算法，這個(gè)算法追求的就是每次匹配，一般發(fā)現(xiàn)失敗了，要往前移動(dòng)盡可能多的距離，少算一點(diǎn)是一點(diǎn)。為了實(shí)現(xiàn)這個(gè)目標(biāo)，首先算法選擇的就是從pattern的尾部開(kāi)始算。這個(gè)時(shí)候就會(huì)出現(xiàn)若干種情況。

Boyer-Moore算法不僅效率高，而且構(gòu)思巧妙，容易理解。1977年，德克薩斯大學(xué)的Robert S. Boyer教授和J Strother Moore教授發(fā)明了這種算法。

（1）Boyer-Moore算法歷史

Boyer-Moore字符串搜索算法是一種非常高效的字符串搜索算法，它由Bob Boyer和J Strother Moore設(shè)計(jì)于1977年

（2） BM算法特點(diǎn)和比較基本流程

1. BM算法特點(diǎn)

● BM算法采用從右向左比較的方法

● 應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來(lái)決定向右跳躍的距離。

● 在BM算法匹配的過(guò)程中，取壞字符規(guī)則和好后綴規(guī)則中跳躍的較大者作為跳躍的距離。

2. BM算法比較基本流程

● BM算法的基本流程：

設(shè)文本串T = abcecabe

模式串為P = abcab

首先將T與P進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 ，如下圖所示:

比較過(guò)程中，若是某次比較不匹配時(shí)，BM算法就采用兩條啟發(fā)式規(guī)則。

即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過(guò)程的結(jié)束。

3. BM： 壞字符規(guī)則和好后綴規(guī)則

壞字符和好后綴的概念

圖中，第一個(gè)不匹配的字符（紅色部分）為壞字符，已匹配部分（綠色）為好后綴。

（3）壞字符規(guī)則

T = abcdabce

P1 = abd

P2 = cdef

在BM算法從右向左掃描的過(guò)程中，若發(fā)現(xiàn)某個(gè)字符x不匹配，則按如下兩種情況討論：

1. 如果字符x在模式P中沒(méi)有出現(xiàn)，那么從字符x開(kāi)始的m個(gè)文本顯然不可能與P匹配成功，直接全部跳過(guò)該區(qū)域即可

（如上面的 T 和 P1 中的T c字符P1中沒(méi)有c）。

2. 如果x在模式P中出現(xiàn)，則以該字符進(jìn)行對(duì)齊。

（如上面的 T 和 P2 中的T c字符P1中有c）

用數(shù)學(xué)公式表示，設(shè)Skip(x)為P右移的距離，m為模式串P的長(zhǎng)度，max(x)為字符x在P中最右位置。

（4）壞字符規(guī)則例子

圖中紅色部分c與b，發(fā)生了一次不匹配。

計(jì)算移動(dòng)距離Skip? = m-max§ = 5 - 3 = 2，則P向右移動(dòng)2位。

移動(dòng)后如下圖：

（5）好后綴規(guī)則

若發(fā)現(xiàn)某個(gè)字符不匹配的同時(shí)，已有部分字符匹配成功，則按如下兩種情況討論：

1. 如果在P中位置t處已匹配部分P’在P中的某位置t’也出現(xiàn)，且位置t’的前一個(gè)字符與位置t的前一個(gè)字符不相同，則將P右移使t’對(duì)應(yīng)t方才的所在的位置。

2. 如果在P中任何位置已匹配部分P’都沒(méi)有再出現(xiàn)，則找到與P’的后綴P”相同的P的最長(zhǎng)前綴x，向右移動(dòng)P，使x對(duì)應(yīng)方才P”后綴所在的位置。

用數(shù)學(xué)公式表示，設(shè)Shift(j)為P右移的距離，m為模式串P的長(zhǎng)度，j 為當(dāng)前所匹配的字符位置，s為t’與t的距離（以上情況i）或者x與P”的距離（以上情況ii）。

1. 看下圖，其后綴T’（藍(lán)色）與P中前綴P’（紅色）匹配，則將P’移動(dòng)到T’的位置。

其中，t` = ab

2. 再下圖中，已匹配部分cab（綠色）在P中再?zèng)]出現(xiàn)