LeetCode面试刷题技巧- 字符串匹配习题集(二)

举报
格图洛书 发表于 2022/06/01 23:52:12 2022/06/01
【摘要】 字符串匹配之Horspool算法 Boyer-Moore-Horspool是一种 字符串匹配 算法,它将从 模式的末尾 到开始比较字符。其首先检查与最后一个模式字符对齐的文本字符,当字符 不匹配 时,搜索跳到模式中的 下一个匹配 位置;如果都不匹配,将模式...

字符串匹配之Horspool算法

Boyer-Moore-Horspool是一种 字符串匹配 算法,它将从 模式的末尾 到开始比较字符。其首先检查与最后一个模式字符对齐的文本字符,当字符 不匹配 时,搜索跳到模式中的 下一个匹配 位置;如果都不匹配,将模式向前移动直到匹配为止。换句话说,Boyer-Moore-Horspool算法是一种在字符串中查找子字符串的算法。

Horspool算法由Nigel Horspool在1980年发表,Nigel Horspool是维多利亚大学的计算机科学教授。该算法时基于Boyer Moore字符串搜索算法的研究,与Knuth Morris Pratt算法相关,旨在创建一种更高效的算法,在最坏情况下达到原始复杂度。

horspool算法将主串中 匹配窗口 的最后一个字符跟模式串中的最后一个字符比较。如果相等,继续从后向前对主串和模式串进行比较,直到完全相等或者在某个字符处不匹配为止(如下图中的α与σ失配) 。如果不匹配,则根据主串匹配窗口中的最后一个字符β在模式串中的下一个出现位置将窗口向右移动。

搜索窗口的理解:

  • 窗口大小与模式串大小相同,窗口内容为文本内容的一部分。

  • 对于窗口而言,每次从后向前匹配&#

文章来源: wenyusuran.blog.csdn.net,作者:文宇肃然,版权归原作者所有,如需转载,请联系作者。

原文链接:wenyusuran.blog.csdn.net/article/details/123678374

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200