Sunday算法是Daniel
M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
假设在发生不匹配时S[i]≠T[j]，1≤i≤N，1≤j≤M。此时已经匹配的部分为u，并假设字符串u的长度为L。如图1。明显的，S[L+i+1]肯定要参加下一轮的匹配，并且T[M]至少要移动到这个位置(即模式串T至少向右移动一个字符的位置)。
图1 Sunday算法不匹配的情况
分如下两种情况：
(1) S[L+i+1]在模式串T中没有出现。这个时候模式串T[0]移动到S[L+i+1]之后的字符的位置。如图2。
图2 Sunday算法移动的第1种情况
(2)S[L+i+1]在模式串中出现。这里S[L+i+1]从模式串T的右侧，即按T[M-1]、T[M-2]、…T[0]的次序查找。如果发现S[L+i+1]和T中的某个字符相同，则记下这个位置，记为k，1≤k≤M，且T[k]=S[L+i+1]。此时，应该把模式串T向右移动M-k个字符的位置，即移动到T[k]和S[L+i+1]对齐的位置。如图3。
图3 Sunday算法移动的第2种情况
Sunday算法思想跟BM算法很相似，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。
现举个例子来说明：
比如：
匹配串：O U R S T R O N G X S E A R C H
模式串：S E A R C H
这里我们看到O-S不相同，我们就看匹配串中的O在模式串的位置，没有出现在模式串中。
匹配串：O U R S T R O N G X S E A R C H
模式串： _ _ _ _ _ _ _ _S E A R C H
移动模式串，使模式串的首字符和O的下一个字符对齐。
匹配串：O U R S T R O N G X S E A R C H
模式串：_ _ _ _ _ _ _ _ S E A R C H
继续比较，N-S不相同，字符R出现在模式串，则后移模式串，将把它们对齐
匹配串：O U R S T R O N G X S E A R C H
模式串： _ _ _ _ _ _ _ _ _ _ _ S E A R C H
#include <iostream>
using namespace std;
bool Appear(const char *s, const char &c)
{
if(s==NULL)
return false;
while(*s!='\0')
{
if(*s==c)
return true;
s++;
}
return false;
}
int Sunday(const char *src, const char *des)
{
if(*src==NULL || *des==NULL)
return 0;
int len_s = strlen(src);
int len_d = strlen(des);
int pos[256];
// cout<<sizeof(pos)<<endl;
// memset(pos,6,1024); //这样是不行的，但是初始化为0还是可以的
int i=0;
for(i=0;i<256;i++)
pos[i] = len_d;
for(i=0; i<len_d; i++) //当src[k]与第一个字符不相等时，需要跳跃的步长
pos[des[i]] = len_d - i; //将src中的位置向后移动到字符串S，按照例子是从N移动到S
for(i=0;i<256;i++)
cout<<pos[i];
cout<<endl;
int index = 0;
int k=0;
bool flag = false;
while(index < len_s)
{
k=index;
for(i=0;i<len_d;i++)
{
if(src[k]!=des[i])
{
index = index + pos[src[k]];
break;
}
else
k++;
}
if(i==len_d)
return index;
if(Appear(des, src[index])) //如果尾字符在des中出现，则移动src
index = k + pos[src[index]]; //这儿不能是index，而是k，因为index会在上面不等的时候多加了一个pos[src[k]];
else
index = index + 1; //如果尾字符不在des中出现，则移动一个值到N
}
return -1;
}
int main()
{
char a[]={"ourstrongxsarchsearchi"};
char b[]={"search"};
cout<<Sunday(a,b)<<endl;
return 0;
}