字符串匹配算法之Sunday算法

背景

我們第一次接觸字符串匹配，想到的肯定是直接用2個循環(huán)來遍歷，這樣代碼雖然簡單，但時間復雜度卻是Ω(m*n)，也就是達到了字符串匹配效率的下限。于是后來人經(jīng)過研究，構造出了著名的KMP算法（Knuth-Morris-Pratt算法），讓我們的時間復雜度降低到了O(m+n)，但現(xiàn)代文字處理器中，卻很少使用KMP算法來做字符串匹配，因為還是太慢了。現(xiàn)在主流的算法是BM算法（Boyer-Moore算法），成功讓平均時間復雜度降低到了O(m/n)，而Sunday算法，則是對BM算法的進一步小幅優(yōu)化。

KMP算法很多人看了一遍遍以后，對next[n]數(shù)組的理解還是有點困難（包括筆者），寫代碼的時候總是容易變成這種情況（/捂臉.jpg）：

（切到網(wǎng)頁）：馬冬梅

（切到編譯器）：馬什么梅

（切到網(wǎng)頁）：馬冬梅

（切到編譯器）：馬冬什么

（切到網(wǎng)頁）：馬冬梅

（切到編譯器）：什么冬梅

而Sunday算法，理解起來則是非常容易，同時極低的時間復雜度，讓Sunday算法成為了筆者目前最常使用的字符串匹配算法

算法解釋

Sunday算法和BM算法稍有不同的是，Sunday算法是從前往后匹配，在匹配失敗時關注的是主串中參加匹配的最末位字符的下一位字符。

• 如果該字符沒有在模式串中出現(xiàn)則直接跳過，即移動位數(shù) = 模式串長度 + 1；
• 否則，其移動位數(shù) = 模式串長度 - 該字符最右出現(xiàn)的位置(以0開始) = 模式串中該字符最右出現(xiàn)的位置到尾部的距離 + 1。

下面舉個例子說明下Sunday算法。假定現(xiàn)在要在主串”substring searching”中查找模式串”search”。

• 剛開始時，把模式串與文主串左邊對齊：

  Sunday算法1

• 結果發(fā)現(xiàn)在第2個字符處發(fā)現(xiàn)不匹配，不匹配時關注主串中參加匹配的最末位字符的下一位字符，即標粗的字符 i，因為模式串search中并不存在i，所以模式串直接跳過一大片，向右移動位數(shù) = 匹配串長度 + 1 = 6 + 1 = 7，從 i 之后的那個字符（即字符n）開始下一步的匹配，如下圖：
  
  Sunday2

• 結果第一個字符就不匹配，再看主串中參加匹配的最末位字符的下一位字符，是’r’，它出現(xiàn)在模式串中的倒數(shù)第3位，于是把模式串向右移動3位（m - 3 = 6 - 3 = r 到模式串末尾的距離 + 1 = 2 + 1 =3），使兩個’r’對齊，如下：

  
  
  Sunday3
• 匹配成功。

詳細代碼（Java版）

static final int ASCII_SIZE = 126;   

int sunday(char[] total,char[] part){
        int tSize = total.length;
        int pSize = part.length;
        int[] move = new int[ASCII_SIZE];
        //主串參與匹配最末位字符移動到該位需要移動的位數(shù)
        for (int i= 0;i<ASCII_SIZE;i++){
            move[i] = pSize+1;
        }
       
        for (int i = 0;i<pSize;i++){
            move[part[i]] = pSize-i;
        }
        
        int s = 0;//模式串頭部在字符串位置
        
        int j;//模式串已經(jīng)匹配了的長度
        
        while(s<=tSize-pSize){//到達末尾之前
            j = 0;
            while(total[s+j]==part[j]){
                j++;
                if (j>=pSize){
                    return s;
                }
            }
            s+=move[total[s+pSize]];
        }
        return -1;
    }

我們來一步一步解釋

int sunday(char[] total,char[] part){
        int tSize = total.length;
        int pSize = part.length;
        ...
        }

其中total為主串，part為模式串

        int[] move = new int[ASCII_SIZE];
        //主串參與匹配最末位字符移動到該位需要移動的位數(shù)
        for (int i= 0;i<ASCII_SIZE;i++){
            move[i] = pSize+1;
        }
        
        for (int i = 0;i<pSize;i++){
            move[part[i]] = pSize-i;
        }

定義一個長為ASCII碼長度大小的數(shù)組，用于存放存入匹配失敗時模式串需要移動的長度。這里看到，除了part中不存在的字符，移動長度都直接是模式串長度+1；而part中存在的字符，則需要移動的長度則依次減小。這也很好理解，因為我們匹配的是模式串首部位置+模式串長度+1位置的字母存在于模式串中的位置，這個位置越靠后，則整個模式串需要移動的距離就越短

        int s = 0;//模式串頭部在字符串位置
        
        int j;//模式串已經(jīng)匹配了的長度

s為模式串首部在字符串的位置，一開始為0；j是模式串已經(jīng)匹配了的長度，一開始也是0

        while(s<=tSize-pSize){ // 1
            j = 0; // 2
            while(total[s+j]==part[j]){// 3
                j++;// 4
                if (j>=pSize){ 
                    return s;// 5
                }
            }
            s+=move[total[s+pSize]]; // 6
        }

這里是最關鍵的代碼了，咱們講細一點

1. 首先循環(huán)繼續(xù)的判定條件為s<=tSize-pSize，s作為模式串首部在字符串的位置，加上pSize肯定要比tSize小，不然就越界了

2. j是模式串已經(jīng)匹配了的長度，匹配開始或者匹配失敗后都要給j賦值為0，重新開始計數(shù)

3. 接下就是一個字符一個字符的比較的循環(huán)

4. 已經(jīng)比較成功，則j加1

5. 如果j已經(jīng)大于等于pSize，就返回模式串首部在字符串當前的位置

6. 這是最關鍵的一句，涉及到Sunday算法的核心，也就是模式串在主串中的“跳躍”，我們把這句代碼分解一下就好理解的多

   int nextCompare = s+pSize; //跳到s+pSize，也就是模式串后的一個字符的位置
   int ascii_number = total[nextCompare];//獲取轉跳后位置的字符的ascii碼值
   int moveLength = move[ascii_number];//根據(jù)ascii碼值在move數(shù)組中查找模式串需要跳躍的長度
   s += moveLength; //讓模式串首部在字符串的位置加上跳躍的長度，完成跳躍
   

一個例子

 String str1 = "searching substring";
 String str2 = "substr";
 sunday(str1.toCharArray(),str2.toCharArray());

其實最關鍵的，就是要計算move[]數(shù)組中的各個值，我們來手動算一下

pSize = 6;
i = 0 : part[i] = s; move[s] = 6;
i = 1 : part[i] = u; move[u] = 5;
i = 2 : part[i] = b; move[b] = 4;
i = 3 : part[i] = s; move[s] = 3;
i = 4 : part[i] = t; move[t] = 2;
i = 5 : part[i] = r; move[r] = 1;

final:
move[s] = 3，
move[u] = 5, 
move[b] = 4, 
move[s] = 3，
move[t] = 2, 
move[r] = 1 , 
move[其他] = 7

然后進行匹配

1. s = 0, j = 1時，匹配失敗

   total[s+pSize] = total[6] = i

   move[i] = 7

   s+=7

   待匹配串為ing substring

2. s = 7 , j = 0 時，匹配失敗

   total[s+pSize] = total[13] = u

   move[u] = 5

   s+=5

   待匹配串為substring

3. 匹配成功

Sunday算法的缺點

看上去簡單高效非常美好的Sunday算法，也有一些缺點。因為Sunday算法的核心依賴于move數(shù)組，而move數(shù)組的值則取決于模式串，那么就可能存在模式串構造出很差的move數(shù)組。例如下面一個例子

主串：baaaabaaaabaaaabaaaa

模式串：aaaaa

這個模式串使得move[a]的值為1，即每次匹配失敗時，只讓模式串向后移動一位再進行匹配。這樣就讓Sunday算法的時間復雜度飆升到了O(m*n)，也就是字符串匹配的最壞情況

總結

當然，也不能因為存在最壞的情況就直接否定Sunday算法，大多數(shù)情況下，Sunday依然是一個簡單高效的算法，值得我們熟練學習掌握。