1,Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。
2,Sunday算法其实思想跟BM算法很相似,只不过Sunday算法是从前往后匹配,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过,即移动步长= 匹配串长度+ 1;否则,同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。
3,举例:
匹配串:abcbczdxzc
模式串:zbcac
这里我们看到z-a没有对上,我们就看匹配串中的z在模式串的位置,然后对齐。
匹配串:abcbczdxzc
模式串: zbcac
如果模式串中的没有那个字符的话就跳过去。
匹配串:abcbcedxzcs
模式串:zbcac
e不在模式串中出现,那么我们就
匹配串:abcbcedxzcs
模式串: zbcac
4,实例代码:
#include <iostream>
#include <cstring>
using namespace std;
int sunday(const char* src, const char* des)
{
int len_s = strlen(src);
int len_d = strlen(des);
int next[26] = {0};
for (int j = 0; j < 26; ++j)
next[j] = len_d + 1;
for (int j = 0; j < len_d; ++j)
next[des[j] - 'a'] = len_d - j; //记录字符到最右段的最短距离+1
//例如:des = "abcedfb"
//next = {7 1 5 4 3 2 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8}
int pos = 0;
while (pos < (len_s - len_d + 1)) //末端对齐
{
int i = pos;
int j;
for (j = 0; j < len_d; ++j, ++i)
{
if (src[i] != des[j])
{
pos += next[src[pos + len_d] - 'a'];
//不等于就跳跃,跳跃是核心
break;
}
}
if ( j == len_d )
return pos;
}
return -1;
}
int main()
{
char src[]="abcdacdaahfacabcdabcdeaa";
char des[]="abcde";
cout<<sunday(src,des)<<endl;
return 0;
}
分享到:
相关推荐
模式匹配之Sunday算法,Sunday算法的说明见文章: http://blog.csdn.net/sun2043430/article/details/8820123
字符串匹配算法之Sunday算法C++实现
Sunday算法特征码搜索极速定位基址和call地址C++(支持通配符),绝对可以用的特征码搜索基址,call的地址。上传备用。
sunday算法,原始文章
BM算法和sunday算法相关的原始论文
SUNDAY 算法 (初步想用它来做字符匹配度的标准) 参考:http://hi.baidu.com/blackcode/blog/item/583d1c38bb3621f3b211c7bd.html
自己所写的sunday算法的实现,初学者所写请见谅!
字符串模式匹配算法 sunday算法实现。说到字符串匹配算法,立马就想到了KMP算法,谁让KMP这么经典呢,各种算法教材里必然有KMP啊。但是KMP算法太复杂了,比KMP更简单更高效的算法就是Sunday算法。
在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是:在字符串从右向左匹配过程中,当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时,...
Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。 核心思想:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行...
字符串匹配算法 Sunday算法 一种线性字符串模式匹配算法 C语言实现。
字符串匹配之Sunday算法(英文原版)
Sunday算法是目前单字符串匹配算法中最快的一种。类似的还有BM
C/C++,判断索引超出了数组的界限的Sunday算法及其源代码
基于Sunday算法改进的字符串匹配算法,张超超,芦天亮,字符串模式匹配算法在入侵检测系统、协议识别技术中起着至关重要的作用。文章在分析几种经典的模式匹配算法的基础上,提出了一种
Sunday算法思想跟BM算法很相似,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符,下面是用C#实现sunday的实例代码,有需要的朋友可以参考一下
Sunday算法的思想和BM算法中的坏字符思想非常类似。差别只是在于Sunday算法在匹配失败之后,是取目标串中当前和Pattern字符串对应的部分后面一个位置的字符来做坏字符匹配,写了个小例子来实现以下这个算法
用C++实现字符串模式匹配算法中的sunday算法