字符串匹配之Sunday算法

简介

Sunday算法是一种字符串匹配算法，相比于KMP算法，它比较简单易学。

在有些时候，比如字符串很长的时候，它是比KMP要高效的。

核心思想

1. 从前往后匹配，匹配失败时关注主串中参与匹配的最末位字符的下一位。

2. 该字符没有在模式串中出现，则直接跳过，且模式串移动位数 = 模式串长度 + 1。

3. 否则，移动位数 = 模式串长度 - 该字符在模式串最右出现出现的位置。

---

这三步说明了具体的执行，感觉很抽象。但综合起来就是：

• 匹配时从前向后匹配。
• 匹配失败时，重新对齐模式串与主串。

所以现在的问题是，这个重新对齐是怎么对齐呢？

举个栗子

• 设主串为 eurusdoveyesido
• 设模式为 esid

1. 正常匹配，在第2位发现不匹配，于是看主串中参与匹配的最末位字符的下一位，也就是s。s也在模式串出现过，那么对齐

2. 对齐后，继续正常匹配，发现第1位就不同，匹配失败。同样，看v，发现v没在模式串出现过，那么模式串就与v后面的e对齐

3. 同样，匹配失败。对齐i

4. 终于，匹配成功！

代码实现

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