Sunday算法詳解

gaoxuqiang 8年前發布 | 28K 次閱讀算法

來自： http://blog.csdn.net/laojiu_/article/details/50767615

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。Sunday算法的思想和BM算法中的壞字符思想非常類似。差別只是在于Sunday算法在失配之后，是取目標串中當前和模式串對應的部分后面一個位置的字符來做壞字符匹配。

如下：
下標數：0 1 2 3 4 5 6 7 8 9 0
目標串：a b c d e f g h i j k
模式串：b x c d

BM算法在b和x失配后，壞字符為b(下標1)，在模式串中尋找b的位置，找到之后就對應上，移到下面位置繼續匹配。
目標串：a b c d e f g h i j k
模式串： b x c d

而在sunday算法中，對于上面的匹配，發現失配后，是取目標串中和模式串對應部分后面的一個字符，也就是e，然后用e來做壞字符匹配。e在模式串中沒有，所以使用sunday算法，接下來會移動到下面的位置繼續匹配。
目標串：a b c d e f g h i j k
模式串： b x c d

從這里可以看出，Sunday算法比BM算法的位移更大，所以Sunday算法比BM算法的效率更高。但是最壞的時間復雜度仍然有o(目標串長度*模式串長度)。考慮這樣的目標串：baaaabaaaabaaaabaaaa，要在里面搜索aaaaa，顯然是沒有匹配位置。但是如果用Sunday算法，壞字符大部分都是a，而模式串中又全部都是a，所以在大部分情況下，發現失配后模式串只能往右移動1位。而如果用改進的KMP算法，仍然是可以保證線性時間內匹配完。

另外，使用Sunday算法不需要固定地從左到右匹配或者從右到左的匹配(這是因為失配之后我們用的是目標串中后一個沒有匹配過的字符)，我們可以對模式串中的字符出現的概率事先進行統計，每次都使用概率最小的字符所在的位置來進行比較，這樣失配的概率會比較大，所以可以減少比較次數，加快匹配速度。

如下面的例子：
目標串：a b c d e f g h i j k
模式串：a a b c c
模式串中b只出現了一次，a,c都出現了2次，所以我們可以先比較b所在的位置（只看模式串中的字符的話，b失配的概率會比較大）。

總之，Sunday算法簡單易懂，思維跳出常規匹配的想法，從概率上來說，其效率在匹配隨機的字符串時比其他匹配算法還要更快。

完整代碼：

#define _CRT_SECURE_NO_DEPRECATE   
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1  

#include<iostream> 
#include<string>

using namespace std;

int _next[256];
string dest;
string pattern;

/*
因為i位置處的字符可能在pattern中多處出現（如下圖所示），而我們需要的是最右邊的位置，這樣就需要每次循環判斷了，非常麻煩，性能差。這里有個小技巧，就是使用字符作為下標而不是位置數字作為下標。這樣只需要遍歷一遍即可，這貌似是空間換時間的做法，但如果是純8位字符也只需要256個空間大小，而且對于大模式，可能本身長度就超過了256，所以這樣做是值得的（這也是為什么數據越大，BM/Sunday算法越高效的原因之一）。
*/
void GetNext()
{
    int len = pattern.size();//get the length

    for (int i = 0; i < 256; i++)
        _next[i] = -1;

    for (int i = 0; i < len; i++)
        _next[pattern[i]] = i;
}

int SundaySearch()
{
    GetNext();

    int destLen = dest.size();
    int patternLen = pattern.size();

    if (destLen == 0) return -1;

    for (int i = 0; i <= destLen - patternLen;)
    {
        int j = i;//dest[j]
        int k = 0;//pattern[k]

        for (; k<patternLen&&j < destLen&&dest[j] == pattern[k]; j++, k++)
            ;//do nothing

        if (k == patternLen)//great! find it!
            return i;
        else
        {
            if (i + patternLen < destLen)
                i += (patternLen - _next[dest[i + patternLen]]);
            else
                return -1;
        }
    }

    return -1;
}

int main()
{
    dest = "This is a wonderful city";

    //case one(successful locating)
    pattern = "wo";
    int result = SundaySearch();
    if (result == -1)
        cout << "sorry,you do not find it!\n";
    else
        cout << "you find it at " << result << endl;

    //case two(unsuccessful locating)
    pattern = "wwe";
    result = SundaySearch();
    if (result == -1)
        cout << "sorry,you do not find it!\n";
    else
        cout << "you find it at" << result << endl;

    return 0;
}

測試：