文档章节

Sunday算法

dclink
 dclink
发布于 2013/03/27 00:07
字数 853
阅读 200
收藏 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
深圳
程序员
很久以前写的一个快速匹配查找算法,非空间换时间。

此算法已通过测试,是多年前自己写的,适合在微内存的设备上应用。比KMP算法快2.5倍,其他类似的算法可以忽视,其超短字串比SUNDAY,BM等算法的查找速度要快。 第一篇原创算法是最近一年闲写...

AL10000
07/23
0
0
模式匹配-概述

模式匹配 模式匹配是字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。假设模式P是给定的子串,目标T是待查找的字符串,要求从目标T中找...

壶漏子
2015/05/25
91
0
字符串匹配-sunday算法

#include<iostream>using namespace std;//匹配字符串。能匹配子串在原始字符串中所有出现的位置的开始下标,下标以0开始。int match(int i, int n, const char ori, const char sub){ int ...

您这磨人的小妖精
2015/09/05
98
0
MatcherDroid-类正则表达式匹配自动机,更高效率,更好中文支持

What’s MatcherDroid 因为不爽正则表达式复杂的语法,较低的中文支持度,不是很好的效率,所以自己写了一个类正则表达式的自动匹配/提取机。目前测试来看,MatcherDroid相较于正则表达式,有...

wxyyxc1992
2013/11/30
0
1
同样的逻辑,为什么JDK自带indexof为何越跑越快,自定indexof不会!

一下是运行结果 -1 1734 vs 1529 38140 443 vs 468 -1 1422 vs 1483 18006 176 vs 203 12596 124 vs 125 93424 1312 vs 219 3237 16 vs 0 76998 1063 vs 0 77389 1123 vs 0 -1 1424 vs 0 第一......

胡建洲
2017/05/04
142
2

没有更多内容

加载失败,请刷新页面

加载更多

搬瓦工最新国内可访问镜像网址:bwh8.net

昨天搬瓦工之前的国内备用镜像网址bwh1.net被域名污染了,在国内打不开了。搬瓦工发布了最新的国内可访问的镜像地址:bwh8.net。 消息来源:搬瓦工优惠网->搬瓦工最新国内可访问镜像网址:b...

flyzy2005
37分钟前
0
0
大数据学习之-NN,SNN和DN的作用

NameNode(名称节点,简称NN)作用: 文件系统命名空间,维护文件系统目录树 存储文件名称, 文件目录结构, 文件属性(权限,大小,创建时间,副本数及大小....), 文件对应的数据块及这些块所...

hnairdb
41分钟前
1
0
TypeScript基础入门之声明合并(三)

转发 TypeScript基础入门之声明合并(三) 声明合并 将命名空间与类,函数和枚举合并 命名空间足够灵活,也可以与其他类型的声明合并。 为此,命名空间声明必须遵循它将与之合并的声明。 生成的...

durban
48分钟前
0
0
webSocket前台实现

webSocket前台实现 简单实现: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <script type="application/javascript" src="js/base64.js"></script......

Airship
59分钟前
1
0
从零到一,使用实时音视频 SDK 一起开发一款 Zoom 吧

zoom(zoom.us) 是一款受到广泛使用的在线会议软件。相信各位一定在办公、会议、聊天等各种场景下体验或者使用过,作为一款成熟的商业软件,zoom 提供了稳定的实时音视频通话质量,以及白板、...

七牛云
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部