【模式比對】之 —— Sunday算法

本文代碼下載下傳位址

http://download.csdn.net/detail/sun2043430/5273911

Sunday算法思路

Sunday算法的思想和BM算法中的壞字元思想非常類似。

差别隻是在于Sunday算法在失配之後，是取目标串中目前和模式串對應的部分後面一個位置的字元來做壞字元比對。 如下圖： 下标數：01234567890 目标串：abcdefghijk 模式串：bxcd

BM算法在b和x失配後，壞字元為b(下标1)，在模式串中尋找b的位置，找到之後就對應上，移到下面位置繼續比對。 目标串：abcdefghijk 模式串： bxcd

而在sunday算法中，對于上面的比對，發現失配後，是取目标串中和模式串對應部分後面的一個字元，也就是e，然後用e來做壞字元比對。 e在模式串中沒有，是以使用sunday算法，接下來會移動到下面的位置繼續比對。 目标串：abcdefghijk 模式串：     bxcd

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

另外，使用Sunday算法不需要固定地從左到右比對或者從右到左的比對(這是因為失配之後我們用的是目标串中後一個沒有比對過的字元)， 我們可以對模式串中的字元出現的機率事先進行統計，每次都使用機率最小的字元所在的位置來進行比較，這樣失配的機率會比較大，是以可以減少比較次數，加快比對速度。 如下面的例子： 目标串：abcdefghijk 模式串：aabcc 模式串中b隻出現了一次，a,c都出現了2次，是以我們可以先比較b所在的位置（隻看模式串中的字元的話，b失配的機率會比較大）。

總之，Sunday算法簡單易懂，思維跳出正常比對的想法，從機率上來說，其效率在比對随機的字元串時比其他比對算法還要更快。

完整的Sunday算法

#include <stdio.h>
#include <string.h>

bool BadChar(const char *pattern, int nLen, int *pArray, int nArrayLen)
{
    if (nArrayLen < 256)
    {
        return false;
    }
    for (int i = 0; i < 256; i++)
    {
        pArray[i] = -1;
    }
    for (int i = 0; i < nLen; i++)
    {
        pArray[pattern[i]] = i;
    }
    return true;
}

int SundaySearch(const char *dest, int nDLen,
                 const char *pattern, int nPLen,
                 int *pArray)
{
    if (0 == nPLen)
    {
        return -1;
    }
    for (int nBegin = 0; nBegin <= nDLen-nPLen; )
    {
        int i = nBegin, j = 0; 
        for ( ;j < nPLen && i < nDLen && dest[i] == pattern[j];i++, j++);
        if (j == nPLen)
        {
            return nBegin;
        }
        if (nBegin + nPLen > nDLen)
        {
            return -1;
        }
        else
        {
            nBegin += nPLen - pArray[dest[nBegin+nPLen]];
        }
    }
    return -1;
}

void TestSundaySearch()
{
    int         nFind;
    int         nBadArray[256]  = {0};
                               //        1         2         3         4
                               //0123456789012345678901234567890123456789012345678901234
    const char  dest[]      =   "abcxxxbaaaabaaaxbbaaabcdamno";
    const char  pattern[][40] = {
        "a",
        "ab",
        "abc",
        "abcd",
        "x",
        "xx",
        "xxx",
        "ax",
        "axb",
        "xb",
        "b",
        "m",
        "mn",
        "mno",
        "no",
        "o",
        "",
        "aaabaaaab",
        "baaaabaaa",
        "aabaaaxbbaaabcd",
        "abcxxxbaaaabaaaxbbaaabcdamno",
    };

    for (int i = 0; i < sizeof(pattern)/sizeof(pattern[0]); i++)
    {
        BadChar(pattern[i], strlen(pattern[i]), nBadArray, 256);
        nFind = SundaySearch(dest, strlen(dest), pattern[i], strlen(pattern[i]), nBadArray);
        if (-1 != nFind)
        {
            printf("Found    \"%s\" at %d \t%s\r\n", pattern[i], nFind, dest+nFind);
        }
        else
        {
            printf("Found    \"%s\" no result.\r\n", pattern[i]);
        }

    }}

int main(int argc, char* argv[])
{
    TestSundaySearch();
	return 0;
}
           

輸出結果：

Found    "a" at 0       abcxxxbaaaabaaaxbbaaabcdamno
Found    "ab" at 0      abcxxxbaaaabaaaxbbaaabcdamno
Found    "abc" at 0     abcxxxbaaaabaaaxbbaaabcdamno
Found    "abcd" at 20   abcdamno
Found    "x" at 3       xxxbaaaabaaaxbbaaabcdamno
Found    "xx" at 3      xxxbaaaabaaaxbbaaabcdamno
Found    "xxx" at 3     xxxbaaaabaaaxbbaaabcdamno
Found    "ax" at 14     axbbaaabcdamno
Found    "axb" at 14    axbbaaabcdamno
Found    "xb" at 5      xbaaaabaaaxbbaaabcdamno
Found    "b" at 1       bcxxxbaaaabaaaxbbaaabcdamno
Found    "m" at 25      mno
Found    "mn" at 25     mno
Found    "mno" at 25    mno
Found    "no" at 26     no
Found    "o" at 27      o
Found    "" no result.
Found    "aaabaaaab" no result.
Found    "baaaabaaa" at 6       baaaabaaaxbbaaabcdamno
Found    "aabaaaxbbaaabcd" at 9         aabaaaxbbaaabcdamno
Found    "abcxxxbaaaabaaaxbbaaabcdamno" at 0    abcxxxbaaaabaaaxbbaaabcdamno
           

本文代碼下載下傳位址

http://download.csdn.net/detail/sun2043430/5273911