文档章节

Sunday算法

dclink
 dclink
发布于 2013/03/27 00:07
字数 853
阅读 217
收藏 0

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

资料1:http://blog.csdn.net/hairetz/article/details/4729397
资料2:http://blog.csdn.net/zhanglizhe_cool/article/details/5576037

Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。其核心思想是:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右 向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。

Sunday算法思想跟BM算法很相似,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过,即移动步长= 匹配串长度+1;否则,同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。

例如我们要在"substring searching"查找"search",刚开始时,把子串与文本左边对齐:

s

u

b

s

t

r

i

n

g

 

s

e

a

r

c

h

i

n

g

s

e

a

r

c

h

 

 

 

 

 

 

 

 

 

 

 

 

 

结果在第二个字符处发现不匹配,于是要把子串往后移动。但是该移动多少呢?这就是各种算法各显神通的地方了,最简单的做法是移动一个字 符位置;KMP是利用已经匹配部分的信息来移动;BM算法是做反向比较,并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那 个字符(上图中的'i')。

显然,不管移动多少,这个字符是肯定要参加下一步的比较的,也就是说,如果下一步匹配到了,这个字符必须在子串内。所以,可以移动子 串,使子串中的最右边的这个字符与它对齐。现在子串'search'中并不存在'i',则说明可以直接跳过一大片,从'i'之后的那个字符开始作下一步的 比较,如下图:

s

u

b

s

t

r

i

n

g

 

s

e

a

r

c

h

i

n

g

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

s

e

a

r

c

h

 

 

 

这次匹配成功了!回顾整个过程,我们只移动了两次子串就找到了匹配位置。可以证明,用这个算法,每一步的移动量都比BM算法要大,所以肯定比BM算法更快。

简单的测试代码:

#include <iostream>
using namespace std;

int sunday(const char *src,const char *des)
{
    int i,j,pos=0;
    int len_s,len_d;
    int next[26]={0};                                //next数组,预处理初始化
    len_s=strlen(src);
    len_d=strlen(des);
    for(j=0;j<26;++j)                       //初始化next数组
        next[j]=len_d + 1;
    for(j=0;j<len_d;++j)                        //设置next数组
        next[des[j]-'a']=len_d-j; 
    while( pos<(len_s-len_d+1) )               //遍历原串          
    {
        i=pos;
        for(j=0;j<len_d;++j,++i)              //比较
        {
            if(src[i]!=des[j])                //一旦不匹配,原串就按照next跳转
            {
                pos+=next[src[pos+len_d]-'a'];
                break;
            }
        }
        if(j==len_d)
            return pos;
    }
    return -1;                               //无子串则返回-1
}

int main()
{
    char src[]="substring searching";
    char des[]="search";
    cout<<sunday(src,des)<<endl;
    return 0;
}


本文转载自:http://sxnuwhui.blog.163.com/blog/static/137068373201251252017480/

dclink

dclink

粉丝 15
博文 44
码字总数 1118
作品 0
深圳
程序员
私信 提问
加载中

评论(0)

自己之前写的匹配查找算法,综合评估都很不错(带注解)

不同于目前最流行的,有碰撞的,空间占用很高的HASH算法。对于普通程序而言,自然希望使用的空间能小点。当然,自己的这个算法自然要比市面上那些KMP,BM,SUNDAY等搜索匹配算法的综合效率要...

osc_q9huomuf
2018/07/08
2
0
Java实现Sunday百万级数据量的字符串快速匹配算法

背景 在平时的项目中,几乎都会用到比较两个字符串时候相等的问题,通常是用==或者equals()进行,这是在数据相对比较少的情况下是没问题的,当数据库中的数据达到几十万甚至是上百万千万的数据需...

osc_tg4e471h
2019/04/01
2
0
Sunday 字符串匹配算法(C++实现)

简介: Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。其核心思想是:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时...

osc_rq37fdad
2019/08/27
1
0
通用高效字符串匹配--Sunday算法

字符串匹配(查找)算法是一类重要的字符串算法(String Algorithm)。有两个字符串, 长度为m的haystack(查找串)和长度为n的needle(模式串), 它们构造自同一个有限的字母表(Alphabet)。如果在hay...

osc_1zmv6tk6
2019/10/17
2
0
字串查找算法总结及MS的strstr源码

http://www.cnblogs.com/ziwuge/archive/2011/12/09/2281455.html 首先来说说字串的查找,即就是在一个指定的字串A中查找一个指定字串B出现的位置或者统计其他B在A中出现的次数等等相关查找。...

shzwork
2019/06/01
15
0

没有更多内容

加载失败,请刷新页面

加载更多

图片转换为pdf可以吗?图片是否可以制作成电子书?

严格来说,PDF文件和图片文件还真的挺像的,图片文件中可以包含有文字、图片等信息,PDF文件中也可以包含有图片、文字等信息,那么问题来了,图片转换为pdf可以吗?我们知道,很多电子书都是...

dawda
18分钟前
23
0
Adobe Dreamweaver CC 2019 安装教程

一、DW简介 Adobe Dreamweaver,简称“DW”,中文名称 "梦想编织者",最初为美国MACROMEDIA公司开发 ,2005年被Adobe公司收购。DW是集网页制作和管理网站于一身的所见即所得网页代码编辑器。...

微笑涛声
19分钟前
17
0
Serverless 选型:深度解读 Serverless 架构及平台选择

作者 | 悟鹏 阿里巴巴技术专家 导读:本文尝试以日常开发流程为起点,分析开发者在每个阶段要面对的问题,然后组合解决方案,提炼面向 Serverless 的开发模型,并与业界提出的 Serverless 产...

osc_sxdofc9c
19分钟前
28
0
pdf图片提取怎么操作?如何提取pdf文档中的图片?

pdf文件的定位便是一款不可编辑的文件,当然,如果要使用pdf中的文字信息,还是很简单的,再不济,咱们可以直接手打,将这些文字信息给打出来,那么如果想要使用的是pdf中的图片信息怎么办呢...

深蓝月上
20分钟前
20
0
MATLAB安装libsvm工具箱的方法

支持向量机(support vector machine,SVM)是机器学习中一种流行的学习算法,在分类与回归分析中发挥着重要作用。基于SVM算法开发的工具箱有很多种,下面我们要安装的是十分受欢迎的libsvm工...

osc_n3mzii7x
20分钟前
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部