字符串匹配之Sunday算法 - 江水为竭 - JOYK Joy of Geek, Geek News, Link all geek

字符串匹配之Sunday算法 - 江水为竭

2 years ago

source link: https://www.cnblogs.com/Az1r/p/16751593.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

字符串匹配之Sunday算法 - 江水为竭 - 博客园

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

__EOF__

Recommend

www.jianshu.com 7 years ago
Cache

进击算法：字符串匹配的 BM 算法 - 简书

进击算法：字符串匹配的 BM 算法 BM 算法介绍各种文本编辑器的 "查找" 功能（Ctrl+F），大多采用 Boyer-Moore 算法。 Boyer-Moore 算法不仅效率高，而且构思巧妙，容易理解。1977 年，德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了这种算法...