详解字符串的快速匹配算法:KMP

作者/分享人:浅浅
向 Ta 提问
目前在闽南师范大学就读,爱好国学与晨跑,痴迷机器学习与数据挖掘,Lisp爱好者。

在字符串匹配算法里,有两种较为常见的方式,BF 算法与 KMP 算法。

BF 算法是指将主串的第 I 个字符与模式串的第1个字符进行比较,如果相等便继续进行比较操作;若不匹配时,回溯到主串的第 I+1 个字符继续与模式串的第1个字符进行比较,直到结果出现。

而 KMP 算法则是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数来实现快速匹配,当出现匹配不相等时,不需要回溯,只需利用已经得到的匹配信息,将模式串向右滑动尽可能远的距离,然后接着继续进行比较即可。

本场 Chat 内容如下:

  1. 介绍简单模式匹配算法(BF 算法)与 KMP 算法的差异;
  2. 以具体的例子来讲解 KMP 算法。
已有146人预订
预订达标
文章出炉
     
18.08.07
18.08.23
本场 Chat 文章已出炉,购买后即可阅读文章并获得一张浅浅的读者圈Pass
请务必添加GitChat服务号以查看活动进度及获取活动通知。
查看文章评论/提问
Vophan Lee
挺好的,只不过我常用python
一季四芳
不好
浅浅: 哪里不好?
浅浅: 刚刚有些急了,毕竟是自己呕心沥血的文章,就好像是自己的笔下花,有生命一样的。在这里我为上一条评论的鲁莽向您道歉。 您要是觉得有哪个地方写的不够全面,或者说写的不够好,浅浅欢迎您指出我的不足之处,这也是一种携手进步的方式嘛。
你可能还喜欢
解读《阿里巴巴 Java 开发手册》背后的思考
Hollis
Python 数据分析师必备的入门学习路线和技能
zglg
LeetCode 刷题指南以及常见算法题解题思路总结
kerry
高并发系统缓存实战入门
饿了么物流技术团队
从零开始做你自己的文字识别系统
天马行空
写一个 IoC/DI 容器来理解 Spring 框架的思想
愚凡
微信扫描登录
关注提示×
扫码关注公众号,获得 Chat 最新进展通知!
添加小助手微信×