Sunday算法详解

gaoxuqiang 8年前

来自： 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;  }

测试：