字符串匹配的KMP算法

程序员之家 · 公众号 · 程序员 · 2017-03-30 20:59

正文

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

推荐文章

OSC开源社区 · 从架构稳定到AI自驱：55个案例拆解大模型落地实战

昨天

程序员小灰 · 我的第一个副业是什么？

3 天前

程序猿 · 我就想问问，中国程序员去日本当程序员容易吗？

昨天

极客之家 · 报表工具为何成为企业成本黑洞？买断制VS按需付费，谁才是降本终极方案？

3 天前

蚂蚁技术AntTech · 清华蚂蚁开源首个全异步强化学习训练系统，SOTA推理大模型RL训练提速2.77倍

2 天前

不贱不散 · 小伙穿婚纱求婚，勇气可嘉！

8 年前

格上财富 · 特斯拉工厂被曝光，整个工厂只有150个机器人，超震撼！

8 年前

高中语文 · 原来满分作文都是这么使用素材的啊，真后悔现在才看到！

8 年前

秋叶PPT · 告别加班的9个Office技巧，你值得拥有！

7 年前

战略前沿技术 · 互联网、脑科学与人工智能，新科学革命的前夜与人类的未来（附演讲PPT）

7 年前