姓名：徐娇 学号：17011210547
转自https://www.61mon.com/index.php/archives/213/
【嵌牛导读】
Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。
其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday 算法的实现可比 KMP，BM 的实现容易太多。
【嵌牛鼻子】Sunday 算法
【嵌牛提问】Sunday 算法代码如何实现？
【嵌牛正文】
算法过程
假定主串为 "HERE IS A SIMPLE EXAMPLE"，模式串为 "EXAMPLE"。
（1）
从头部开始比较，发现不匹配。则 Sunday 算法要求如下：找到主串中位于模式串后面的第一个字符，即红色箭头所指的 “空格”，再在模式串中从后往前找“空格”，没有找到，则直接把模式串移到“空格” 的后面。
（2）
（3）
找到匹配。
完整代码
/**
*
* author : 刘毅（Limer）
* date : 2017-07-30
* mode : C++
*/
#include
#include
#defineMAX_CHAR256
#defineMAX_LENGTH1000
usingnamespacestd;
voidGetNext(string&p,int&m,intnext[])
{
for(inti=0;i
next[i]= -1;
for(inti=0;i
next[p[i]]=i;
}
voidSunday(string&s,int&n,string&p,int&m)
{
intnext[MAX_CHAR];
GetNext(p,m,next);
intj;// s 的下标
intk;// p 的下标
inti=0;
while(i<=n-m)
{
j=i;
k=0;
while(j
j++,k++;
if(k==m)
cout<<"在"<
if(i+m
i+=(m-next[s[i+m]]);
else
return;
}
// PS: 匹配失败不作处理
}
intmain()
{
strings,p;
intn,m;
while(cin>>s>>p)
{
n=s.size();
m=p.size();
Sunday(s,n,p,m);
cout<
}
return0;
}
数据测试如下图：
