C++ SUNDY算法（BM算法的改进）

科技前沿 • 2025-01-05 15:54 • 阅读 84

大家好，我是讯享网，很高兴认识大家。

字符串查找算法中，最著名的两个是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; }

讯享网

C++ SUNDY算法（BM算法的改进）

相关推荐