Sunday算法是Daniel M.Sunday于1990年提出的字元串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过儘可能多的字元以进行下一步的匹配，从而提高了匹配效率。
基本介绍
- 中文名：sunday 算法
- 外文名：Sunday Algorithm
- 人物：Daniel M.Sunday
- 时间：1990年
- 类属：字元串模式匹配
算法介绍
Sunday是一个线性字元串模式匹配算法。算法的概念如下：
Sunday算法是Daniel M.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匹配。
这时我们就寻找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时，匹配完毕。
Sunday算法思想跟BM算法很相似，在匹配失败时关注的是文本串中参加匹配的最末位字元的下一位字元。如果该字元没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+1；否则，同BM算法一样其移动步长=匹配串中最右端的该字元到末尾的距离+1。
算法举例
S:abcceabcaabcd
T:abcd
发现d与c不匹配。此时S[L+M+1]=='e'，没有出现在T中。于是：
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党：（也没多大区别）
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=c.length()-1; lend=d.length()-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;}
