horspool算法讲解_string匹配字符串

horspool算法讲解_string匹配字符串Horsepool算法是Boyer-Moore算法的简化版本,这也是一个空间换时间的典型例子。算法把模式P和文本T的开头字符对齐,从模式的最后一个字符开始比较,如果尝试比较失败了,它把模式向后移。每次尝试过程中比较是从右到左的。假设文本中,对齐模式最后一个字符的元素是c,Horspool算法根据c的不同情况来确定移动距离,无论c是否和模式的最后一个字符相匹配。一般来说,会存在下面四种情况。情况1:看

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Horsepool算法是Boyer-Moore算法的简化版本,这也是一个空间换时间的典型例子。算法把模式P和文本T的开头字符对齐,从模式的最后一个字符开始比较,如果尝试比较失败了,它把模式向后移。每次尝试过程中比较是从右到左的。

假设文本中,对齐模式最后一个字符的元素是c,Horspool算法根据c的不同情况来确定移动距离,无论c是否和模式的最后一个字符相匹配。

一般来说,会存在下面四种情况。

这里写图片描述

情况1:看第一行,模式中不存在c(此时c就是字母A),模式的移动长度就是它的全部长度,移到第二行所示的位置。

情况2:看第二行,c(此时c就是字符O)正好是模式的最后一个字符,但是从右向左比较时,有字符不匹配,比如此时的AE不匹配。而且模式中的其他m-1个字符也不包含c。移动的情况类似情况1,移动的幅度等于模式的全部长度,移到第三行所示的位置。

这里写图片描述
情况3:看第一行,模式中存在c(此时c就是字符L),但是它不是模式的最后一个字符,移动时应该把模式中最右边的c和文本中的c对齐,移到第二行所示的位置。
情况4:看第二行,c(此时c就是字符O)正好是模式的最后一个字符,但是从右向左比较时,有字符不匹配,比如此时的AE不匹配。而此时模式中的其他m-1个字符包含c。移动的情况类似情况3,移动时应该把前m-1个字符中最右边的c和文本中的c对齐,移到第三行所示的位置。

这说明,比起蛮力算法每次总是移动一个位置,从右到左的字符比较使模式模式移动得更远。然而,如果在每次尝试时都必须检查模式中的每个字符,它的优势也会丧失殆尽。我们可以预先算出遇到某个字符要移动的距离,并把它存在一个表中。具体来说,对于每一个字符c,可以通过以下公式算出移动距离:

t(c)={
mm1ccm-1

如对于模式BARBER,移动距离如下表所示:

字符c A B E R 其它字符(包括空格,标点符号,下划线和其它一些特殊字符)
移动距离t(c) 4 2 1 3 6

c++实现

int Horspool(vector<char> & T,vector<char> & P)
{
    int n = T.size();
    int m = P.size();   
    vector<int> table(96,m);//以字母表中可打印字符为索引的数组

    for(int i = 0;i < m - 1;i++)
    {
        table[P[i] - 32] = m - 1 - i;//模式串中每个字符的移动距离,从左至右扫描模式,相同字符的最后一次改写恰好是该字符在模式串的最右边
    }

    int i = m - 1;
    while(i <= n - 1)
    {
        int k = 0;
        while(k <= m - 1 && P[m - 1 - k] == T[i - k])
            k++;

        if(k == m)
            return i - m + 1;//匹配成功,返回索引
        else
            i += table[T[i] - 32];//模式串向右移动
    }

    return -1;//匹配失败
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171722.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java uniqueresult_「uniqueresult」hibernate uniqueResult方法 – seo实验室[通俗易懂]

    java uniqueresult_「uniqueresult」hibernate uniqueResult方法 – seo实验室[通俗易懂]uniqueresult数据库中根据你的查询条件只会返回唯一结果,就可以用uniqueresult这个方法!否则就用list();其返回类型为ObjectuniqueResult()方法通常是在业务方法查询语句中用到的,比如(Usersroles)getsession().createQuery(“selecturfromUsersRolesurwhereur.role.id=?…

  • python interpolate.interp1d,Python interp1d与UnivariateSpline

    python interpolate.interp1d,Python interp1d与UnivariateSplineI’mtryingtoportsomeMatLabcodeovertoScipy,andI’vetriedtwodifferentfunctionsfromscipy.interpolate,interp1dandUnivariateSpline.Theinterp1dresultsmatchtheinterp1dMatLabfunctio…

  • 接口测试题目_jmeter接口自动化测试框架

    接口测试题目_jmeter接口自动化测试框架http接口工具有很多如:postman、jmeter、soupUI、Java+httpclient、robotframework+httplibrary、Fidder+postman等1、什么是接口接口就是内部模块对模块,外部系统对其他服务提供的一种可调用或者连接的能力的标准接口的种类和分类:webservice和httpapi接口1)webservice接口是走soap协议通过htt…

  • 软件安装管家(2021年4月15更新)

    软件安装管家(2021年4月15更新)在网上看到许多小伙伴在问软件安装管家公众号为什么不能用了,在这里就把他们的一些资源整理出来分享给大家啦!各位观众老爷赶紧点赞收藏吧!软件导航①电脑系统 ②办公软件③图像处理④影视动画⑤AutoCAD⑥3D设计⑦机械设计⑧建筑设计⑨网页设计⑩开发编程⑪数据分析⑫仿真模拟⑬行业软件软件目录①电脑系统 安装环境PE工具箱Vmware(虚拟机)Windows10U盘安装win10直接安装win10虚拟机装win10Win10官方原版镜像文件下载地址汇总Windows7U盘安装win7直接安装

  • 硬件基础知识(6)—电容分类[通俗易懂]

    硬件基础知识(6)—电容分类[通俗易懂]智能硬件和物联网产品上,工作电压不高,其常用的电容根据不同的工艺,主要分为陶瓷电容、电解电容和钽电容。↑陶瓷电容的结构图↑电解电容的结构图不管是什么电容,都是两组金属片夹着一层介质。陶瓷电容把金属片交错摆放,电解电容把金属片卷成柱状。↑片状陶瓷电容↑贴片陶瓷电容陶瓷电容,MultilayerCeramicCapacitor(MLCC),陶瓷电容的电介质是陶瓷,所以叫做陶瓷电容。陶瓷电容容值小、…

  • 50个Java精品源码免积分下载[通俗易懂]

    50个Java精品源码免积分下载[通俗易懂]JAVA开发缺不了代码。代码的数量众多,质量也参差不齐。如果在多如繁星的代码世界中找到最适合自己的无异于大海捞针,所以我为大家搜集了不少优质的代码资源,希望大家喜欢。JAVA开发和PHP开发的OA系统性能比较【源代码】http://down.51cto.com/data/572164Java课程设计案例精编光盘源码【源代码】http://down.51cto.com/data/57

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号