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

作者/分享人:浅浅
向 Ta 提问
目前就读于闽南师范大学,喜欢唱、跳、rap和篮球。

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

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

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

本场 Chat 内容如下:

  1. 介绍简单模式匹配算法(BF 算法)与 KMP 算法的差异;
  2. 以具体的例子来讲解 KMP 算法。
已有152人预订
预订达标
文章出炉
     
18.08.07
18.08.23
本场 Chat 文章已出炉,购买后即可阅读文章并获得一张浅浅的读者圈Pass
请务必添加GitChat服务号以查看活动进度及获取活动通知。
查看文章评论/提问
Vophan Lee
挺好的,只不过我常用python
一季四芳
不好
浅浅: 哪里不好?
浅浅: 刚刚有些急了,毕竟是自己呕心沥血的文章,就好像是自己的笔下花,有生命一样的。在这里我为上一条评论的鲁莽向您道歉。 您要是觉得有哪个地方写的不够全面,或者说写的不够好,浅浅欢迎您指出我的不足之处,这也是一种携手进步的方式嘛。
你可能还喜欢
JVM 问题诊断快速入门
火币集团研发中心
面试字节跳动的一点小经验
Wayne
互联网公司热门面试题:如何保证缓存与数据库的双写一致性?
魏武归心2016
面试官问:为什么在项目中使用消息队列!到底是想考什么?
零下
小程序 · 云开发实战:从 0 到 1 快速开发电商小程序
微信极客WeGeek
如何做好性能压测(二) | 性能压测工具选型对比
阿里巴巴中间件
微信扫描登录
关注提示×
扫码关注公众号,获得 Chat 最新进展通知!
入群与作者交流×
扫码后回复关键字 入群
Chat·作者交流群
入群码
该二维码永久有效