开发者社区> 问答> 正文

目前时间复杂度最好的字符串匹配算法是什么

如题。能简要叙述下更好。谢谢了。

展开
收起
知与谁同 2018-07-20 20:01:02 3657 0
3 条回答
写回答
取消 提交回答
  • 楼上是只知道 KMP 吗?O(n+m) 也能叫最低?

    BM,BMH,Sunday 哪个不比 KMP 低,甚至更简单的 RK 平时用着也和 KMP 差不多。KMP 虽然很经典,但是也不能什么都扯 KMP 吧。

    2020-10-20 17:09:12
    赞同 展开评论 打赏
  • KMP算法,最大的特点是指示主串的指针你需要回溯,真个匹配的过程中,对主串仅需从头至尾扫描一遍,这对处理从外设输入的庞大文件很有效,可以边读入变匹配,无需回头重读。
    2019-07-17 22:56:03
    赞同 展开评论 打赏
  • KMP是O(n+m),你可以上网搜索一下。
    还有扩展KMP,是针对不同的问题。
    以及Trie等多模式匹配。
    总之都能方便搜索到啦。
    2019-07-17 22:56:03
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载