文档章节

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
ES6对对象的拓展(2018-05-08)

对象的传统表示法 let person = { "name":"张三", "say":function(){ alert("你好吗?"); } } ES6中的简洁写法 var name = "Zhangsan"; var age = 12; //传统的属性写法 var person = { "na......

a小磊_
05/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

windbg调试C源码级驱动

联机方式不多说了。我博客里有,英文的。 windbg联机文档 https://docs.microsoft.com/zh-cn/windows-hardware/drivers/debugger/debug-universal-drivers---step-by-step-lab--echo-kernel......

simpower
33分钟前
0
0
redis快照和AOF简介

数据持久化到硬盘:一是快照(snapshotting),二是只追加文件(append-only file AOF) 快照 核心原理:redis某个时间内存内的所有数据写入硬盘 场景:redis快照内存里面的数据 1. 用户发送bgsav...

拐美人
33分钟前
0
0
这个七夕,送你一份程序员教科书级别的告白指南

给广大爱码士们的高能预警: 今天,就是七夕了…… (单身非作战人群请速速退场!) 时常有技术GG向个推君抱怨 经过网民多年的教育 以及技术人持之以恒的自黑 冲锋衣狂热分子·格子衫骨灰级粉...

个推
38分钟前
0
0
python爬虫日志(15)cookie详解

转载:原文地址 早期Web开发面临的最大问题之一是如何管理状态。服务器端没有办法知道两个请求是否来自于同一个浏览器。那时的办法是在请求的页面中插入一个token,并且在下一次请求中将这个...

茫羽行
39分钟前
0
0
qlv视频格式转换器

  腾讯视频中的视频影视资源有很多,小编经常在里面下载视频观看,应该也有很多朋友和小编一样吧,最近热播的电视剧也不少,如《香蜜沉沉烬如霜》、《夜天子》还有已经完结的《扶摇》,这么...

萤火的萤火
42分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部