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

Sunday算法是DanielM.Sunday在1990年提出的字符串

模式匹配

。基本思想是：在匹配过程中找到模式匹配。如果无法匹配，算法可以跳过尽可能多的字符进行下一步匹配，从而提高匹配效率。中文名称类别字符串模式匹配

Sunday是一个线性字符串

模式匹配

算法。算法的概念如下：

Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配

算法。基本思想是：模式匹配过程不需要从左到右或从右到左比较。如果发现不匹配，算法可以尽可能跳过。 角色

用于下一步匹配，从而提高匹配效率。

令模式串分别为S、子串T、长度N和M。对于

T，我们进行一个简单而智能的预处理：将每个字符的最后一个位置存储在中 T 并将其存储在数组中。

假设出现不匹配时，S[i]≠T[j]，1≤i≤N，1≤j≤M。设S中第一个匹配字母的位置为本次L。显然，S[L+M+1]必须参与下一轮匹配，而T必须至少匹配S[L+M+1]。可以匹配整个S。

我们现在正在寻找 S[L+M+1] 在 T 中出现的地方。使用预处理后的数组，我们在 O(1) 中找到位置 u 并将其直接移动到 T[u]==S[L+M+1]。具体来说，如果T中没有出现S[L+M+1]，则T无法匹配S[L+M+1]，则将T的第一位直接移至S[L+M+2]，继续匹配。直到L+M>N匹配完成。

Sunday 算法背后的思想与 BM 算法非常相似。如果匹配失败，它将关注匹配的文本字符串的最后一个字符之后的下一个字符。如果该字符没有出现在匹配字符串中，则直接跳过，即移动步长=匹配字符串长度+1；否则与 BM 算法相同，移动步长 = 从最右边的字符到匹配字符串末尾的距离 + 1 。

S:abcceabcaabcd

T:abcd

发现d与c不匹配。目前T中不显示S[L+M+1]=='e'。所以：

S: abcceabcaabcd

T:--------abcd

发现d与a不对应。当前S[L+M+1]=='a'，T出现在T[0]的最后。所以：

S:abcceabcaabcd

T:--------------abcd

匹配成功。

递归代码，请见谅

数组方：

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方：（差别不大）