比起流行的kmp算法, Sunday不仅搜索效率上要高很多, 而且原理还特别简单易理解, 也容易实现.
字符串匹配——Sunday算法
基本思想及举例
Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似.
Sunday算法是:从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。
下面举个例子说明下Sunday算法。假定现在要在主串”instroiuctionxy”中查找模式串”iuc”。
刚开始时，把模式串与文主串左边对齐：
结果发现在第2个字符处发现不匹配，不匹配时关注主串中参加匹配的最末位字符的下一位字符，即标红的字符 t，因为模式串iuc中并不存在t，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 3 + 1 = 4，从t 之后的那个字符（即字符r）开始下一步的匹配，如下图：
结果第一个字符就不匹配，再看主串中参加匹配的最末位字符的下一位字符，是u，它出现在模式串中的倒数第2位，于是把模式串向右移动1位（3 - 2 )，使两个’u’对齐，如下：
匹配成功。
回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高。
====================================================================
c 语言实现代码:
#include <stdio.h>
#include <string.h>
const int NUM=1024;
int sunday(const char* src, const char* des)
{
int jump[NUM]; //映射表 被搜寻字符的ascii码作为jump数组元素的下标---> 元素的值是模式串中该字符对应的主字符串移动位数
int len_d =strlen(des);
int len_s = strlen(src);
for(int p = 0; p < NUM; p++) { //构建映射表,给所有字符对应跳动的位数赋最大值=模式字符串的长度+1
jump[p] = len_d + 1;
}
for(int k = 0; k < len_d; k++) { k是模式字符串中字符的位置, jump数组中相应字符对应的值= 模式字符串长度-k
jump[des[k]] = len_d - k;
}
int j=0;
int pos=0;
int end=len_s-len_d;
while(pos<=end) {
j=0;
while( src[pos+j]==des[j]) //主字符串与模式字符串比较
{
j++;
if(j>=len_d)
return pos;
}
pos=pos+jump[src[pos+len_d]]; //字符串指针跳动
}
return -1;
}
int main()
{
char s[]="faddd3fgh4wgfh[ 得齄grcp3";
char d[]="得齄";
int pos= sunday(s,d);
printf("pos=%d\n",pos);
return 0;
}