开发者社区 问答 正文

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

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

展开
收起
知与谁同 2018-07-20 20:01:02 3686 分享 版权
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
    赞同 展开评论