栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

Knuth-Morris-Pratt和Boyer-Moore搜索算法之间的主要区别是什么?

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Knuth-Morris-Pratt和Boyer-Moore搜索算法之间的主要区别是什么?

Moore的UTexas网页逐步介绍了这两种算法(他还提供了各种技术资料):

  • 克努斯·莫里斯·普拉特
  • 博耶·摩尔

据该人本人说,

经典的Boyer-
Moore算法遭受以下现象的困扰:它无法在像DNA这样的小字母上高效地工作。跳过距离往往会随着模式长度的增长而停止增长,因为子字符串会频繁出现。通过记住更多已经匹配的内容,可以在文本中获得更大的跳过。一个人甚至可以安排``完美的记忆’‘,因此最多只能查看每个字符一次,而Boyer-
Moore算法虽然是线性的,但可以多次检查文本中的字符。其他人已经在文献中探讨了这种记住更多的想法。它需要非常大的表或状态机。

但是,对BM进行了一些修改,使小字母搜索变得可行。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/660503.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号