Boyer- Moore算法

主要特徵

假設文本串text長度為n，模式串pattern長度為m，BM算法的主要特徵為：

-從右往左進行比較匹配（一般的字元串搜尋算法如KMP都是從左往右進行匹配）；

-算法分為兩個階段：預處理階段和搜尋階段；

-預處理階段時間和空間複雜度都是是O(m+)，是字元集大小，一般為256；

-搜尋階段時間複雜度是O(mn)；

-當模式串是非周期性的，在最壞的情況下算法需要進行3n次字元比較操作；

-算法在最好的情況下達到O(n/m)，比如在文本串b中搜尋模式串ab ，只需要n/m次比較。

算法基本思想

常規的匹配算法移動模式串的時候是從左到右，而進行比較的時候也是從左到右的，基本框架是：

j = 0;
while (j <= (strlen(text)-strlen(pattern)))
{
    
    
    for (i = 0; i < strlen(pattern) && pattern[i] == text[i+j]; ++i);
    
    
    if (i == strlen(pattern))
    
   
    {
        
        
        Match;
        
        
        break;
    
    
    }
    
    
    else
       
         
        ++j;
 
}

而BM算法在移動模式串的時候是從左到右，而進行比較的時候是從右到左的，基本框架是：

j = 0;
while（j <= (strlen(text)-strlen(pattern))）
{
    
    
for (i = strlen(pattern); i >= 0 && pattern[i] == text[i + j]; --i);
    
    
if (i < 0)) 
    
    {
        
        Match;
        
        break;
    
    }
    
    else
        
        j += BM();
 
}

BM算法的精華就在於BM(text, pattern),也就是BM算法當不匹配的時候一次性可以跳過不止一個字元。即它不需要對被搜尋的字元串中的字元進行逐一比較，而會跳過其中某些部分。通常搜尋關鍵字越長，算法速度越快。它的效率來自於這樣的事實：對於每一次失敗的匹配嘗試，算法都能夠使用這些信息來排除儘可能多的無法匹配的位置。即它充分利用待搜尋字元串的一些特徵，加快了搜尋的步驟。

BM算法實際上包含兩個並行的算法（也就是兩個啟發策略）：壞字元算法（bad-character shift）和好後綴算法（good-suffix shift）。這兩種算法的目的就是讓模式串每次向右移動儘可能大的距離（即上面的BM( )儘可能大）。

字元風暴

大家來頭腦風暴下：如何加快字元串搜尋？舉個很簡單的例子，如下圖所示，navie表示一般做法，逐個進行比對，從右向左，最後一個字元c與text中的d不匹配，pattern右移一位。但大家看一下這個d有什麼特徵？pattern中沒有d，因此你不管右移1、2、3、4位肯定還是不匹配，何必花這個功夫呢？直接右移5（strlen(pattern)）位再進行比對不是更好嗎？好，就這樣做，右移5位後，text中的b與pattern中的c比較，發現還是不同，這時咋辦？b在pattern中有所以不能一下右移5位了，難道直接右移一位嗎？No，可以直接將pattern中的b右移到text中b的位置進行比對，但是pattern中有兩個b，右移哪個b呢？保險的辦法是用最右邊的b與text進行比對，為啥？下圖說的很清楚了，用最左邊的b太激進了，容易漏掉真正的匹配，圖中用最右邊的b後發現正好所有的都匹配成功了，如果用最左邊的不就錯過了這個匹配項嗎？這個啟發式搜尋就是BM算法做的。