字符串匹配算法之Sunday算法(转)

字符串匹配算法之Sunday算法

背景

我们第一次接触字符串匹配，想到的肯定是直接用2个循环来遍历，这样代码虽然简单，但时间复杂度却是Ω(m*n)，也就是达到了字符串匹配效率的下限。于是后来人经过研究，构造出了著名的KMP算法（Knuth-Morris-Pratt算法），让我们的时间复杂度降低到了O(m+n)，但现代文字处理器中，却很少使用KMP算法来做字符串匹配，因为还是太慢了。现在主流的算法是BM算法（Boyer-Moore算法），成功让平均时间复杂度降低到了O(m/n)，而Sunday算法，则是对BM算法的进一步小幅优化。

KMP算法很多人看了一遍遍以后，对next[n]数组的理解还是有点困难（包括笔者），写代码的时候总是容易变成这种情况（/捂脸.jpg）：

（切到网页）：马冬梅

（切到编译器）：马什么梅

（切到网页）：马冬梅

（切到编译器）：马冬什么

（切到网页）：马冬梅

（切到编译器）：什么冬梅

而Sunday算法，理解起来则是非常容易，同时极低的时间复杂度，让Sunday算法成为了笔者目前最常使用的字符串匹配算法

算法解释

Sunday算法和BM算法稍有不同的是，Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。

下面举个例子说明下Sunday算法。假定现在要在主串”substring searching”中查找模式串”search”。

刚开始时，把模式串与文主串左边对齐：

Sunday算法1

结果发现在第2个字符处发现不匹配，不匹配时关注主串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下图：

Sunday2
结果第一个字符就不匹配，再看主串中参加匹配的最末位字符的下一位字符，是’r’，它出现在模式串中的倒数第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];
        //主串参与匹配最末位字符移动到该位需要移动的位数
        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;//模式串已经匹配了的长度
        
        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];
        //主串参与匹配最末位字符移动到该位需要移动的位数
        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码长度大小的数组，用于存放存入匹配失败时模式串需要移动的长度。这里看到，除了part中不存在的字符，移动长度都直接是模式串长度+1；而part中存在的字符，则需要移动的长度则依次减小。这也很好理解，因为我们匹配的是模式串首部位置+模式串长度+1位置的字母存在于模式串中的位置，这个位置越靠后，则整个模式串需要移动的距离就越短

        int s = 0;//模式串头部在字符串位置
        
        int j;//模式串已经匹配了的长度

s为模式串首部在字符串的位置，一开始为0；j是模式串已经匹配了的长度，一开始也是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
        }

这里是最关键的代码了，咱们讲细一点

首先循环继续的判定条件为s<=tSize-pSize，s作为模式串首部在字符串的位置，加上pSize肯定要比tSize小，不然就越界了
j是模式串已经匹配了的长度，匹配开始或者匹配失败后都要给j赋值为0，重新开始计数
接下就是一个字符一个字符的比较的循环
已经比较成功，则j加1
如果j已经大于等于pSize，就返回模式串首部在字符串当前的位置

这是最关键的一句，涉及到Sunday算法的核心，也就是模式串在主串中的“跳跃”，我们把这句代码分解一下就好理解的多

int nextCompare = s+pSize; //跳到s+pSize，也就是模式串后的一个字符的位置
int ascii_number = total[nextCompare];//获取转跳后位置的字符的ascii码值
int moveLength = move[ascii_number];//根据ascii码值在move数组中查找模式串需要跳跃的长度
s += moveLength; //让模式串首部在字符串的位置加上跳跃的长度，完成跳跃

一个例子

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

其实最关键的，就是要计算move[]数组中的各个值，我们来手动算一下

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

然后进行匹配

s = 0, j = 1时，匹配失败

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

move[i] = 7

s+=7

待匹配串为ing substring
s = 7 , j = 0 时，匹配失败

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

move[u] = 5

s+=5

待匹配串为substring
匹配成功

Sunday算法的缺点

看上去简单高效非常美好的Sunday算法，也有一些缺点。因为Sunday算法的核心依赖于move数组，而move数组的值则取决于模式串，那么就可能存在模式串构造出很差的move数组。例如下面一个例子

主串：baaaabaaaabaaaabaaaa

模式串：aaaaa

这个模式串使得move[a]的值为1，即每次匹配失败时，只让模式串向后移动一位再进行匹配。这样就让Sunday算法的时间复杂度飙升到了O(m*n)，也就是字符串匹配的最坏情况

总结

当然，也不能因为存在最坏的情况就直接否定Sunday算法，大多数情况下，Sunday依然是一个简单高效的算法，值得我们熟练学习掌握。