sunday算法

sunday算法是字符串模式匹配算法,是在BM算法上的优化.
提出者: Daniel M.Sunday(1990)
核心思想:在匹配过程中, 模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较, 它在发现不匹配时, 算法能跳过尽可能多的字符以进行下一步的匹配, 从而提高了匹配效率.

简单匹配过程:
文本为:“substring searching algorithm”
字串为:“search”
刚开始时, 把子串与文本左边对齐:

substring searching algorithm
search

结果在第二个字符处发现不匹配, 于是要把子串往后移动. 但是该移动多少呢？
这就是各种算法各显神通的地方了, 最简单的做法是移动一个字符位置;

KMP是利用已经匹配部分的信息来移动;BM算法是做反向比较, 并根据已经匹配的部分来确定移动量.
这里要介绍的方法是看紧跟在当前子串之后的那个字符 （第一个字符串中的’i’).
显然, 不管移动多少, 这个字符是肯定要参加下一步的比较的.
也就是说, 如果下一步匹配到了, 这个字符必须在子串内.

所以, 可以移动子串, 使子串中的最右边的这个字符与它对齐. 现在子串’search’中并不存在’i’, 则说明可以直接跳过一大片, 从’i’之后的那个字符开始作下一步的比较, 如下:

substring searching algorithm
search

比较的结果, 第一个字符就不匹配, 再看子串后面的那个字符, 是’r’,它在子
串中出现在倒数第三位, 于是把子串向后移动三位, 使两个’r’对齐, 如下:

substring searching algorithm
search

这次匹配成功了！
上面一段例子摘自:http://blog.chinaunix.net/uid-25513153-id-225240.html
C语言实现:

/*************************** 
sunday algorithm
By: QbeensLee
Date:2013/11/17
****************************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define LIMITED 1000000
char a[LIMITED],b[LIMITED];
inline int sunday(char *text, char *key)
{
	if(!(*key))return 0;
	int ans=0,tag,size_match;
	int i,limit,shift[256],len_text=strlen(text),len_key=strlen(key); 
	if(len_key>len_text)
		return 0;
	char *match;
	for(i=0;i<256;i++)
		shift[i]=len_key+1;
	for(i=0;i<len_key;++i)
		shift[*(key+i)]=len_key-i;
	limit=len_text-len_key+1;
	for(i=0;i<limit;i+=shift[text[len_key+i]])
	{
		if(*(text+i)==*key)
		{
			match=text+i+1;
			size_match=1;
			do
			{
				if(size_match==len_key)
					ans++;
			}while((*match++)==key[size_match++]);
		}
	}
	return ans;
}

int main()
{
	//freopen("a.in","r",stdin);
	int n;
	scanf("%d%*c",&n);
	while(n--)
	{
		gets(a);
		gets(b);
		printf("%d\n",sunday(b,a));
	}
	return 0; 
}

但在ACM的OJ上, 实用sunday算法成功解决KMP算法是不太容易的,往往会超时, 这因为这些题目摆明了是要用KMP算法做的.

KMP比较适合在文本中大量重复出现子串的匹配, So~ ~ OJ上的测试数据都是对KMP算法有利.

但在实用性和易懂性上讲,我还是比较喜欢sunday算法的.

推荐阅读:
Sunday algorithm
Quick Search algorithm
改进的Sunday模式匹配算法

文章作者: qbeenslee