简介
Sunday算法是一种字符串匹配算法，相比于KMP算法，它比较简单易学。
在有些时候，比如字符串很长的时候，它是比KMP要高效的。
核心思想
- 从前往后匹配，匹配失败时关注主串中参与匹配的最末位字符的下一位。
- 若该字符没有在模式串中出现，则直接跳过，且模式串移动位数 = 模式串长度 + 1。
- 否则，移动位数 = 模式串长度 – 该字符在模式串最右出现出现的位置。
这三步说明了具体的执行，感觉很抽象。但综合起来就是：
- 匹配时从前向后匹配。
- 匹配失败时，重新对齐模式串与主串。
所以现在的问题是，这个 重新对齐是怎么对齐呢？
举个栗子
- 设主串为 eurusdoveyesido
-
设模式串为 *esid
-
正常匹配，在第2位发现不匹配，于是看 主串中参与匹配的最末位字符的下一位，也就是 s。 s也在模式串出现过，那么对齐
- 对齐后，继续正常匹配，发现第1位就不同，匹配失败。同样，看 v，发现 v没在模式串出现过，那么模式串就与 v后面的 e对齐
- 同样，匹配失败。对齐 i
- 终于，匹配成功！
代码实现
_next数组
是的，Sunday算法也有next数组需要预处理。
next数组存储的是：模式串不同字符最右边的下标。
所以，对于上面例子的模式串 esid
- (next[d] = 3)
- (next[i] = 2)
- (next[s] = 1)
- (next[e] = 0)
而对于英文字符，它们都在ASCII里，总计256个，所以我们开一个256大小的数组
int _next[256];
void getnext(char pattern[])
{
int len = strlen(pattern);
int i;
for(i = 0;i < 256; i ++)//初始化为 -1
{
_next[i] = -1;
}
int cnt = 0;
for(i = len - 1;i >= 0;i --)
{
if(_next[i] == -1)
{
_next[(int)pattern[i]] = i;
cnt ++;
if(cnt == 256)//256满了就退出
{
break;
}
}
}
}
这样的预处理，正是以空间换取时间
匹配过程
匹配的代码按思想写就好，值得一提的是：
因为模式串中没有出现的字符的 next值为 -1，所以正好，当要对齐的时候，模式串多向后移动了一位（减 负 1 -> 加 1）。
int SundaySearch(char pattern[],char dest[])
{
getnext(pattern);
int i, j, k;
int lenp = strlen(pattern),lend = strlen(dest);
for(i = 0;i < lend;)
{
j = i;
for(k = 0;k < lenp && j < lend; k ++)//匹配的过程
{
if(dest[j] == pattern[k])
{
j ++;
}else
{
break;
}
}
if(k == lenp)//匹配成功，返回首字符下标
{
return i;
}else
{
if(i + lenp < lend)//注意越界
{
i += lenp - _next[(int)dest[i + lenp]];
}
else
{
return -1;
}
}
}
return -1;
}
Original: https://www.cnblogs.com/Az1r/p/16751593.html
Author: 江水为竭
Title: 字符串匹配之Sunday算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/801504/
转载文章受原作者版权保护。转载请注明原作者出处！