bm模式匹配算法原理

1、BM模式匹配算法原理（圖解）模式匹配算法原理（圖解）修改瀏覽權(quán)限|刪除首先，先簡單說明一下有關(guān)BM算法的一些基本概念。BM算法是一種精確字符串匹配算法（區(qū)別于模糊匹配）。BM算法采用從右向左比較的方法，同時應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來決定向右跳躍的距離。BM算法的基本流程:設(shè)文本串T，模式串為P。首先將T與P進(jìn)行左對齊，然后進(jìn)行從右向左比較，如下圖所示:若是某趟比較不匹配時，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符

2、規(guī)則和好后綴規(guī)則，來計算模式串向右移動的距離，直到整個匹配過程的結(jié)束。下面，來詳細(xì)介紹一下壞字符規(guī)則和好后綴規(guī)則。首先，詮釋一下壞字符和好后綴的概念。請看下圖：圖中，第一個不匹配的字符（紅色部分）為壞字符，已匹配部分（綠色）為好后綴。1）壞字符規(guī)則（）壞字符規(guī)則（Badacter）：）：在BM算法從右向左掃描的過程中，若發(fā)現(xiàn)某個字符x不匹配，則按如下兩種情況討論：i.如果在P中位置t處已匹配部分P在P中的某位置t也出現(xiàn)，且位置t的前一個

3、字符與位置t的前一個字符不相同，則將P右移使t對應(yīng)t方才的所在的位置。ii.如果在P中任何位置已匹配部分P都沒有再出現(xiàn)，則找到與P的后綴P相同的P的最長前綴x，向右移動P，使x對應(yīng)方才P后綴所在的位置。用數(shù)學(xué)公式表示，設(shè)Shift(j)為P右移的距離，m為模式串P的長度，j為當(dāng)前所匹配的字符位置，s為t與t的距離（以上情況i）或者x與P的距離（以上情況ii）。以上過程有點(diǎn)抽象，所以我們繼續(xù)圖解。例2：下圖中，已匹配部分cab（綠色）在P