1. Sunday算法是Daniel M.Sunday于1990年提出的一種比BM算法搜尋速度更快的算法。
2. Sunday算法其實思想跟BM算法很相似，隻不過Sunday算法是從前往後比對，
在比對失敗時關注的是文本串中參加比對的最末位字元的下一位字元。
如果該字元沒有在比對串中出現則直接跳過，即移動步長= 比對串長度+ 1；
否則，同BM算法一樣其移動步長=比對串中最右端的該字元到末尾的距離+1。
3. 舉例如下：
//pos=0;
//比對串：abcdacdaahfacabcdabcdeaa
//模式串：abcde
//這裡我們看到a-e沒有對上，我們就看比對串中的pos+len2在模式串的位置，然後對齊。
//比對串：abcdacdaahfacabcdabcdeaa
//模式串： abcde
//pos=3;
//這裡我們看到d-a沒有對上，我們就看比對串中的pos+len2在模式串的位置，然後對齊。
//比對串：abcdacdaahfacabcdabcdeaa
//模式串： abcde
//pos=8;
//這裡我們看到h-b沒有對上，我們就看比對串中的pos+len2在模式串的位置，然後對齊。
//比對串：abcdacdaahfacabcdabcdeaa
//模式串： abcde
//pos=13;
//這裡我們看到c-b沒有對上，我們就看比對串中的pos+len2在模式串的位置，然後對齊。
//比對串：abcdacdaahfacabcdabcdeaa
//模式串： abcde
//pos=17;
//這裡我們看到模式串完全比對 代碼示範如下：
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 char T[10001];
6 char P[26];
7 int next[26];
8
9 int sunday(const char* T, const char* P)
10 {
11 int len1=strlen(T);
12 int len2=strlen(P);
13 memset(next,0,sizeof(next));
14
15 for(int j=0; j<26;++j)
16 next[j]=len2+1;
17 for(j=0; j<len2;++j)
18 {
19 next[P[j]-'a']=len2-j; //記錄字元到最右段的最短距離+1
20 //cout<<"next["<<P[j]-'a'<<"]="<<next[P[j]-'a']<<endl;
21 }
22 //例如:p[]="abcedfb"
23 //next = {7 6 5 4 3 2 1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8}
24
25 int pos = 0;
26 while(pos<(len1-len2+1)) //末端對齊
27 {
28 int i=pos;
29 int j;
30 for(j=0;j<len2;++j,++i)
31 {
32 if(T[i]!=P[j]) //不等于就跳躍,跳躍是核心
33 {
34 pos+= next[T[pos + len2]-'a'];
35 //cout<<"pos="<<pos<<endl<<endl;
36 break;
37 }
38 }
39 if(j==len2)
40 return pos;
41 }
42 return -1;
43 }
44 int main()
45 {
46 char T[]="abcdacdaahfacabcdabcdeaa";
47 char P[]="abcde";
48 while(scanf("%s%s",T,P)!=EOF)
49 cout<<sunday(T,P)<<endl;
50 return 0;
51 } 轉載于:https://www.cnblogs.com/lmei/p/3340681.html