文档章节

字符串搜索的Sunday算法

y
 yky20190625
发布于 07/22 10:38
字数 877
阅读 8
收藏 0

比起流行的kmp算法,  Sunday不仅搜索效率上要高很多, 而且原理还特别简单易理解,  也容易实现.

 

字符串匹配——Sunday算法

基本思想及举例

Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似.

Sunday算法是:从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

i n s t r o i u c t i o n x y
i u c

 

 

如果该字符没有在模式串中出现则直接跳过,即移动位数 = 模式串长度 + 1;
否则,其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。
下面举个例子说明下Sunday算法。假定现在要在主串”instroiuctionxy”中查找模式串”iuc”。

刚开始时,把模式串与文主串左边对齐: 


结果发现在第2个字符处发现不匹配,不匹配时关注主串中参加匹配的最末位字符的下一位字符,即标红的字符 t,因为模式串iuc中并不存在t,所以模式串直接跳过一大片,向右移动位数 = 匹配串长度 + 1 = 3 + 1 = 4,从t 之后的那个字符(即字符r)开始下一步的匹配,如下图: 


结果第一个字符就不匹配,再看主串中参加匹配的最末位字符的下一位字符,是u,它出现在模式串中的倒数第2位,于是把模式串向右移动1位(3 - 2 ),使两个’u’对齐,如下: 


匹配成功。

回顾整个过程,我们只移动了两次模式串就找到了匹配位置,缘于Sunday算法每一步的移动量都比较大,效率很高。

====================================================================

c   语言实现代码:

#include <stdio.h>
#include <string.h>
const int NUM=256;

int sunday(const char* src, const char* des)
{
    unsigned char  jump[NUM];    //映射表   被搜寻字符的ascii码作为jump数组元素的下标---> 元素的值是模式串中该字符对应的主字符串移动位数 
    int  len_d =strlen(des);
    int  len_s = strlen(src);
    
    for(int p = 0; p < NUM; p++) {   //构建映射表,给所有字符对应跳动的位数赋最大值=模式字符串的长度+1 
        jump[p] = len_d + 1;
    }
    for(int k = 0; k < len_d; k++) {  k是模式字符串中字符的位置,  jump数组中相应字符对应的值= 模式字符串长度-k 
        jump[des[k]] = len_d - k;
    }
    
    int j=0;
    int pos=0;
    int end=len_s-len_d;
    while(pos<=end) {
    
        j=0;
        while( src[pos+j]==des[j]) //主字符串与模式字符串比较
        {
            j++;
            if(j>=len_d)
                return pos;
        }
       //由于src中有可能有汉字,  src[pos+len_d] 有可能是汉字双字节中的一个字节, 则可能为负数, 作为下标代入jump数组时, 造成数组越界,因此要将

        // src[pos+len_d] 强制转化为无符号整数 

       pos=pos+jump[ (unsigned char)(src[pos+len_d]) ];   //字符串指针跳动
        
    }
    return  -1;
    
}
int main()
{
    char  s[]="faddd3fgh4wgfh[ 得齄grcp3";
    char  d[]="得齄";
    int pos= sunday(s,d);
    printf("pos=%d\n",pos);
    return 0;
}

 

© 著作权归作者所有

y
粉丝 0
博文 10
码字总数 13594
作品 0
荆州
私信 提问
模式匹配-概述

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

壶漏子
2015/05/25
129
0
MatcherDroid-类正则表达式匹配自动机,更高效率,更好中文支持

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

王下邀月熊
2013/11/30
288
1
JavaScript 字符串匹配算法

原文链接 前言 字符串匹配算法,在日常开发中也常被频繁用到。当然,我们可以用正则匹配来完成字符串匹配,但是,学习和理解相关的字符串匹配算法,对于我们技术成长还是有很多好处的。 定义...

Checkson
07/25
0
0
字串查找算法总结及MS的strstr源码

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

shzwork
06/01
6
0
字符串匹配——Sunday算法

字符串匹配——Sunday算法 基本思想及举例 Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似:1 只不过Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最...

shzwork
06/09
14
0

没有更多内容

加载失败,请刷新页面

加载更多

Qt qml 自定义消息提示框

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/a844651990/article/details/78376767 Qt qml 自定义消息提...

shzwork
昨天
5
0
Linux安装JDK

(rpm) ⒈下载:https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html ⒉安装 rpm -ivh jdk-8u202-linux-x64.rpm ⒊配置环境变量 vim /etc/profile 添加......

无名氏的程序员
昨天
2
0
The POM for xxx is invalid, transitive dependencies (if any) will not be available

The POM for xxx is invalid, transitive dependencies (if any) will not be available, enable debug logging for more details 问题描述 在使用maven打包时,log信息中打印出:[**WARNIN......

lwenhao
昨天
6
0
setState() called after dispose() flutter

# 在setState前加入以下判断if (!mounted) return;

zdglf
昨天
4
0
docker和docker-compose二种方式安装mysql8.0

Docker方式安装 在命令行下运行 docker run -d -p 3306:3306 --restart always --privileged=true--name mysql-e MYSQL_USER="test" -e MYSQL_PASSWORD="test" -e MYSQL_ROOT_PASSWOR......

小白的成长
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部