字符串匹配之Sunday算法

时间:2022-10-04 07:17:41

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

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

核心思想

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

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

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


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

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

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

举个栗子

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

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

字符串匹配之Sunday算法


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

字符串匹配之Sunday算法


  1. 同样,匹配失败。对齐i

字符串匹配之Sunday算法


  1. 终于,匹配成功!

字符串匹配之Sunday算法

代码实现

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