Sunday算法：模式串匹配效率提高

记模式串为S，子串为T，长度分别为N，M。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

对于T，我们做一个简单而巧妙的预处理：记录T中每一种字符最后出现的位置，将其存入一个数组中。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

假设在发生不匹配时S[i]≠T[j]，1≤i≤N，1≤j≤M。设S此次第一个匹配的字符位置为L。显然，S[L+M+1]肯定要参加下一轮的匹配，并且T至少要与S[L+M+1]匹配才有可能与整个S匹配。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

这时我们就寻找T中S[L+M+1]出现的位置了。利用我们预处理好的数组，可以O(1)查找出那个位置u，并将其直接移动至T[u]==S[L+M+1]。特殊地，若S[L+M+1]没有在T中出现，那么T不可能会与S[L+M+1]匹配，则将T的第一位直接移动到S[L+M+2]，继续匹配。直至L+M>N时，匹配完毕。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

Sunday算法思想跟BM算法很相似，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

S:abcceabcaabcd文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

T:abcd文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

发现d与c不匹配。此时S[L+M+1]=='e'，没有出现在T中。于是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

S:abcceabcaabcd文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

T:--------abcd文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

发现d与a不匹配。此时S[L+M+1]=='a'，T中最后出现在T[0]。于是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

S:abcceabcaabcd文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

T:--------------abcd文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

成功匹配。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

递归代码，求神犇轻虐文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

数组党：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

int wei[301]={0};
int ans=0,lend,lenc,tot=0;//tot用于统计匹配次数，便于直观地与其他算法比较
char c[10001],d[10001];
void pei()
{
    int w=0;
    while(w+lend<=lenc)
    {
        int i=0;
        bool f=false;
        while(i<=lend && f==false)
        {
            if(c[i+w]!=d[i])f=true;
            i++;tot++;
        }
        if(f==false){ans++;w++;}
        else
        {
            i=lend+1;
            if(wei[c[i+w]]==-1)w=w+i+1;
            else w=w+i-wei[c[w+i]];
        }
    }
    return;
}
int main()
{
    gets(c);
    gets(d);
    lenc=strlen(c)-1;
    lend=strlen(d)-1;
    for(int i=0;i<=300;++i)wei[i]=-1;
    for(int i=0;i<=lend;++i)
    wei[d[i]]=i;
    pei();
    if(ans)
    cout<<ans<<endl<<tot;
    else cout<<"mission failed";
    return 0;
}

STL党：（也没多大区别）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10838.html

int wei[301]={0};
int ans=0,lend,lenc,tot=0;
string c,d;
void pei()
{
    int w=0;
    while(w+lend<=lenc)
    {
        int i=0;
        bool f=false;
        while(i<=lend && f==false)
        {
            if(c[i+w]!=d[i])f=true;
            i++;tot++;
        }
        if(f==false){ans++;w++;}
        else
        {
            i=lend+1;
            if(wei[c[i+w]]==-1)w=w+i+1;
            else w=w+i-wei[c[w+i]];
        }
    }
    return;
}
int main()
{
    cin>>c;
    cin>>d;
    lenc=()-1;
    lend=()-1;
    for(int i=0;i<=300;++i)wei[i]=-1;
    for(int i=0;i<=lend;++i)
    wei[d[i]]=i;
    pei();
    if(ans)
    cout<<ans<<endl<<tot;
    else cout<<"mission failed";
    return 0;
}