字符串匹配--Sunday算法

字符串匹配(查找)算法是一类重要的字符串算法(String Algorithm)。有两个字符串, 长度为m的haystack(查找串)和长度为n的needle(模式串), 它们构造自同一个有限的字母表(Alphabet)。如果在haystack中存在一个与needle相等的子串，返回子串的起始下标，否则返回-1。C/C++、PHP中的strstr函数实现的就是这一功能。LeetCode上也有类似的题目，比如#28、#187.

这个问题已经被研究了n多年，出现了很多高效的算法，比较著名的有，Knuth-Morris-Pratt 算法 (KMP)、Boyer-Moore搜索算法、Rabin-Karp算法、Sunday算法等。
提出Sunday算法的人叫Sunday，怎么就不能起些狂拽酷炫吊炸天的名字比如hurricane algorithm/bazinga algorithm 之类的呢？-_-||

针对这个问题，Brut-force的解法很直观：两个串左端对其，然后从needle的最左边字符往右逐一匹配，如果出现失配，则将needle往右移动一位，继续从needle左端开始匹配...如此，直到找到一串完整的匹配，或者haystack结束。时间复杂度是O(mn)，看起来不算太糟。入下图所示：
图中红色标记的字母表示第一个发生失配的位置，绿色标记的是完整匹配的位置。

重复这个匹配、右移的过程，每次只将needle右移一个位置

直到找到这么个完整匹配的子串。

限制这个算法效率的因素在于，有很多重复的不必要的匹配尝试。因此想办法减少不必要的匹配，就能提高效率咯。很多高效的字符串匹配算法，它们的核心思想都是一样样的，想办法利用部分匹配的信息，减少不必要的尝试。
Sunday算法利用的是发生失配时查找串中的下一个位置的字母。还是用图来说明：

上图的查找中，在haystack[1]和needle[1]的位置发生失配，接下来要做的事情，就是把needle右移。在右移之前我们先把注意力haystack[3]=d这个位置上。如果needle右移一位，needle[2]=c跟haystack[3]对应，如果右移两位，needle[1]=b跟haystack[3]对应，如果移三位，needle[0]=a跟haystack[3]对应。然后无论以上情况中的哪一种，在haystack[3]这个位置上都会失配(当然在这个位置前面也可能失配)，因为haystack[3]=d这个字母根本就不存在于needle中。因此更明智的做法应该是直接移四位，变成这样：

然后我们发现在needle[0]=a，haystack[4]=b位置又失配了，于是沿用上一步的思路，看看haystack[7]=b。这次我们发现字母b是在needle中存在的，那它就有可能形成一个完整的匹配，因为我们完全直接跳过，而应该跳到haystack[7]与needle[1]对应的位置，如下图：

这一次，我们差点就找到了一个完整匹配，可惜needle[0]的位置失配了。不要气馁，再往后，看haystack[9]=z的位置，它不存在于needle中，于是跳到z的下一个位置，然后...:

于是我们顺利地找到了一个匹配！
然后试着从上面的过程中总结出一个算法来。

输入: haystack, needle
Init: i=0, j=0
while i<=len(haystack)-len(needle):
    j=0
    while j<len(needle) and haystack[i+j] equals needle[j]:
        j=j+1
    if j equals len(needle):
        return i
    else
        increase i...

这里有一个问题，发生失配时，i应该增加多少。如果haystack[i+j]位置的字母不存在于needle中，我们知道可以跳到i+j+1的位置。而如果chr=haystack[i+j]存在于needle，我们说可以跳到使chr对应needle中的同一个字母的位置。但问题是，needle中可能有不止一个的字母等于chr。这种情况下，应该跳到哪一个位置呢？为了不遗漏可能的匹配，应该是跳到使得needle中最右一个chr与haystack[i+j]对应，这样跳过的距离最小，且是安全的。
于是我们知道，在开始查找之前，应该做一项准备工作，收集Alphabet中的字母在needle中最右一次出现的位置。我们建立一个O(k)这么大的数组，k是Alphabet的大小，这个数组记录了每一个字母在needle中最右出现的位置。遍历needle，更新对应字母的位置，如果一个字母出现了两次，前一个位置就会被后一个覆盖，另外我们用-1表示根本不在needle中出现。
用occ表示这个位置数组，求occ的过程如下：

输入： needle
Init: occ is a integer array whose size equals len(needle)
fill occ with -1
i=0
while i<len(needle):
    occ[needle[i]]=i
return occ

还有一点需要注意的是，Sunday算法并不限制对needle串的匹配顺序，可以从左往右扫描needle，可以从右往左，甚至任何自定义的顺序。
接下来尝试具体实现一下这个算法，以下是Java程序，这里假设Alphabet就是ASCII字符集。

    public int strStr(String haystack, String needle) {
        int m=haystack.length(), n=needle.length();
        int[] occ=getOCC(needle);
        int jump=0;
        for(int i=0;i<=m-n; i+=jump){
            int j=0;
            while(j<n&&haystack.charAt(i+j)==needle.charAt(j))
                j++;
            if(j==n)
                return i;
            jump=i+n<m ? n-occ[haystack.charAt(i+n)] : 1;
        }
        return -1;
    }

    public int[] getOCC(String p){
        int[] occ=new int[128];
        for(int i=0;i<occ.length;i++)
            occ[i]=-1;
        for(int i=0;i<p.length();i++)
            occ[p.charAt(i)]=i;
        return occ;
    }

现在来分析一下算法。除去预处理阶段计算occ数组，Sunday算法的主要操作是匹配字符和移动（改变haystack的游标i）。算法的时间复杂度主要依赖两个因素，一是i每次能跳过的位置有多少；二是在内部循环尝试匹配时，多快能确定是失配了还是完整匹配了。在最好的情况下，每次失配，occ[haystack[i+j]]都是-1，于是每次i都跳过n+1个位置；并且当在内部循环尝试匹配，总能在第一个字符位置就确定失配了，这样得到时间O(m/n)。比如下图这种情况：

最坏情况下，每次i都只能移动一位，且总是几乎要到needle的末尾才发现失配了。时间复杂度是O(m*n)并不比Brut-force的解法好。比如像这样：

前面提到Sunday算法对needle的扫描顺序是没有限制的。为了提高在最坏情况下的算法效率，可以对needle中的字符按照其出现的概率从小到大的顺序扫描，这样能尽早地确定失配与否。
Sunday算法实际上是对Boyer-Moore算法的优化，并且它更简单易实现。其论文中提出了三种不同的算法策略，结果都优于Boyer-Moore算法。

Reference:
[1] D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990)
[2] Fachhochschule Flensburg

本文遵守知识共享协议：署名-非商业性使用-相同方式共享 (BY-NC-SA)及简书协议转载请注明：作者曾会玩