数据结构与算法系列----Sunday算法详解

时间:2023-01-03 16:43:17
一:背景

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP,BM的实现容易太多。


二:分析

假设我们有如下字符串:
A = "LESSONS TEARNED IN SOFTWARE TE";
B = "SOFTWARE";
Sunday算法的大致原理是:
先从左到右逐个字符比较,以我们的字符串为例:
开始的时候,我们让i = 0, 指向A的第一个字符; j = 0 指向B的第一个字符,分别为"L"和"S",不等;这个时候,Sunday算法要求,找到位于A字串中位于B字符串后面的第一个字符,即下图中 m所指向的字符"T",在模式字符串B中从后向前查找是否存在"T",

数据结构与算法系列----Sunday算法详解

可以看到下图中k指向的字符与m指向的字符相等,
数据结构与算法系列----Sunday算法详解

这时就将相等的字符对齐,让j再次指向B字符串的头一个字符,相应地,将i指向主串对应的字符N,

数据结构与算法系列----Sunday算法详解

再次比较A[i]和B[j],不等,这时再次寻找主串中在模式串后面的那个字符,

数据结构与算法系列----Sunday算法详解

我们看到,模式串的最后一个字符与m指向的主串字符相等,因此再次移动子串,

数据结构与算法系列----Sunday算法详解

这时,主串i对应的字符是S,j对应的子串字符也是S,i++, j++,

数据结构与算法系列----Sunday算法详解

现在再次不等,m指向字符"D",

数据结构与算法系列----Sunday算法详解


三:完整代码
#define _CRT_SECURE_NO_DEPRECATE   
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1  

#include<iostream> 
#include<string>

using namespace std;

int _next[256];
string dest;
string pattern;

/*
因为i位置处的字符可能在pattern中多处出现(如下图所示),而我们需要的是最右边的位置,这样就需要每次循环判断了,非常麻烦,性能差。这里有个小技巧,就是使用字符作为下标而不是位置数字作为下标。这样只需要遍历一遍即可,这貌似是空间换时间的做法,但如果是纯8位字符也只需要256个空间大小,而且对于大模式,可能本身长度就超过了256,所以这样做是值得的(这也是为什么数据越大,BM/Sunday算法越高效的原因之一)。
*/
void GetNext()
{
	int len = pattern.size();//get the length

	for (int i = 0; i < 256; i++)
		_next[i] = -1;

	for (int i = 0; i < len; i++)
		_next[pattern[i]] = i;
}

int SundaySearch()
{
	GetNext();

	int destLen = dest.size();
	int patternLen = pattern.size();

	if (destLen == 0) return -1;

	for (int i = 0; i <= destLen - patternLen;)
	{
		int j = i;//dest[j]
		int k = 0;//pattern[k]

		for (; k<patternLen&&j < destLen&&dest[j] == pattern[k]; j++, k++)
			;//do nothing

		if (k == patternLen)//great! find it!
			return i;
		else
		{
			if (i + patternLen < destLen)
				i += (patternLen - _next[dest[i + patternLen]]);
			else
				return -1;
		}
	}

	return -1;
}

int main()
{
	dest = "This is a wonderful city";
	
	//case one(successful locating)
	pattern = "wo";
	int result = SundaySearch();
	if (result == -1)
		cout << "sorry,you do not find it!\n";
	else
		cout << "you find it at " << result << endl;

	//case two(unsuccessful locating)
	pattern = "wwe";
	result = SundaySearch();
	if (result == -1)
		cout << "sorry,you do not find it!\n";
	else
		cout << "you find it at" << result << endl;

	return 0;
}

测试:

数据结构与算法系列----Sunday算法详解




返回目录---->数据结构与算法目录





参考:

图片资源采集自:符串匹配算法 – Sunday算法------->http://www.cnblogs.com/lbsong/archive/2012/05/25/2518188.html

字符串搜索算法Boyer-Moore由浅入深(比KMP快3-5倍)----->http://blog.jobbole.com/52830/

字符串匹配的Boyer-Moore算法------>http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

【模式匹配】之 —— Sunday算法------>http://blog.csdn.net/sunnianzhong/article/details/8820123