C++ SUNDY算法(BM算法的改进)

简介:

字符串查找算法中,最著名的两个是KMP算法Knuth-Morris-Pratt)和BM算法(Boyer-Moore)。两个算法在最坏情

况下均具有线性的查找时间。BM算法往往比KMP算法快上3-5倍。但是BM算法还不是最快的算法,这里介绍一种比BM算法更快一些的查找算法。

例如我们要在"substringsearchingalgorithm"查找"search"

第一步,把子串与文本左边对齐:

s u b s t r i n g s e a r c h i n g a l g o r i t h m

s e a r c h

结果在第二个字符处发现不匹配,于是要把子串往后移动。

但是该移动多少呢?

最简单的做法是移动一个字符位置;

KMP是利用已经匹配部分的信息来移动;

BM算法是做反向比较,并根据已经匹配的部分来确定移动量。

而SUNDY算法是看紧跟在当前子串之后的那个字符(第一个字符串中的'i')。


显然,不管移动多少,这个字符是肯定要参加下一步的比较的,也就是说,如果下一步匹配到了,这个字符必须在子串内。

所以,可以移动子串,使子串中的最右边的这个字符与它对齐。

现在子串'search'中并不存在'i',则说明可

以直接跳过一大片,从'i'之后的那个字符开始作下一步的比较,如下:

s u b s t r i n g s e a r c h i n g a l g o r i t h m

                s e a r c h

比较的结果,第一个字符就不匹配,再看子串后面的那个字符,是'r',

它在子串中出现在倒数第三位,于是把子串向后移动三位,使两个'r'对齐,如下:

s u b s t r i n g  s e a r c h i n g a l g o r i t h m

                         s e a r c h

这次匹配成功了!回顾整个过程,我们仅仅移动了两次子串就找到了匹配位置,

可以证明,用这个算法,每一步的移动量都比BM算法要大,所以肯定比BM算法更快。


下面是实现代码:

#include <iostream>
#include <string>
using namespace std;

void SUNDAY(char *text, char *patt)
{
	register size_t temp[256];
	size_t *shift = temp;
	size_t i, patt_size = strlen(patt), text_size = strlen(text);
	cout << "size : " << patt_size << endl;
	for( i=0; i < 256; i++ )
	{
		*(shift+i) = patt_size+1;
	}
	for( i=0; i < patt_size; i++ )
	{
		*(shift + (unsigned char)(*(patt+i))) = patt_size-i;
	}
	//shift['s']=6 步,shitf['e']=5 以此类推
	size_t limit = text_size - patt_size+1;
	for(i=0; i < limit; i += shift[ text[i+patt_size] ])
	{
		if( text[i] == *patt )
		{
			char *match_text = text + i + 1;
			size_t match_size = 1;
			do
			{
				// 输出所有匹配的位置
				if( match_size == patt_size )
				{
					cout << "the NO. is " << i << endl;
				}
			}while((*match_text++) == patt[match_size++]);
		}
	}
	cout << endl;
}
int main(void)
{
	char *text = new char[100];
	text = "substring searching algorithm search";
	char *patt = new char[10];
	patt = "search";
	SUNDAY(text, patt);
	return 0;
}



目录
相关文章
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
451 0
高精度算法(加、减、乘、除,使用c++实现)
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
22 0
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)