目前时间复杂度最好的字符串匹配算法是什么
如题。能简要叙述下更好。谢谢了。
展开
收起
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
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赞同 展开评论
相关问答