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;}