文档章节

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
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
字符串匹配-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
Linux操作系统下账号管理命令及文件介绍

命令: #useradd sunday -->添加用户 useradd -u 720 -g 100 -M -s /bin/bash sunday -M 不建立根目录 -d 指定根目录 -s 使用的shell #passwd sunday -->为用户添加密码 #usermod –L sunda......

JavaGG
2009/05/23
100
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
14分钟前
0
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
17分钟前
2
0
让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字

让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字: 作者:孙冬梅;以前读韩国前总统朴槿惠的著作《绝望锻炼了我》时,里面有一句话令我印象深刻,她说“在我最困难的时期,...

原创小博客
今天
3
0
JAVA-四元数类

public class Quaternion { private final double x0, x1, x2, x3; // 四元数构造函数 public Quaternion(double x0, double x1, double x2, double x3) { this.x0 = ......

Pulsar-V
今天
17
0
Xshell利用Xftp传输文件,使用pure-ftpd搭建ftp服务

Xftp传输文件 如果已经通过Xshell登录到服务器,此时可以使用快捷键ctrl+alt+f 打开Xftp并展示Xshell当前的目录,之后直接拖拽传输文件即可。 pure-ftpd搭建ftp服务 pure-ftpd要比vsftp简单,...

野雪球
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部