Sunday

Sunday

部分资料来自

https://blog.csdn.net/u013949069/article/details/71909779

https://blog.csdn.net/q547550831/article/details/51860017

---

Daniel M.Sunday于1990年提出，它与BM算法类似

在一定程度上比KMP算法和BM算法更优。

但是该算法最坏情况下的时间复杂度为O(mn)

过程

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

情况一：

如上，i失配了，i没出现过，移动模式串长度len+1

情况二

r出现了，与BM算法里坏字符规则类似

移动len-pat_pos：

对比

Sunday算法比较于BM算法，它的坏字符规则保证了跳转值必定大于1

代码

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int index[256];
int main()
{
    memset(index,0,sizeof(index));
	string s1,s2;
    cin>>s1>>s2;
    int len=s1.size();
	for(int i=0;i<len;i++)
        index[(int)s1[i]]=i; //Hashed
    int pos=0,sum=0;//pos->target_string position
    while(pos+len<=s2.size())
    {
        int curpos=0;//curpos->pattern_string position
        for(;curpos<len;curpos++)
        {
            if(s1[curpos]!=s2[curpos+pos])break;
        }
        if(curpos==len)
        {
            sum++;
        }
        if(pos+len>=s2.size())break;
        pos+=len-index[(int)s2[pos+len]];
    }
    cout<<sum<<endl;
    return 0;
}

问题

依然遇到aaaa...去匹配aaaa...会拉垮，复杂度直接O(mn)，实际应用，如文本匹配中很难遇到此类退化情况，但在竞赛里一组数据就足够卡掉了，慎用