KMP算法（研究总结，字符串）
KMP算法（研究总结，字符串）
前段时间学习KMP算法，感觉有些复杂，不过好歹是弄懂啦，简单地记录一下，方便以后自己回忆。
引入
首先我们来看一个例子，现在有两个字符串A和B，问你在A中是否有B，有几个？为了方便叙述，我们先给定两个字符串的值
A="abcaabababaa"
B="abab"
那么普通的匹配是怎么操作的呢？
当然就是一位一位地比啦。（下面用蓝色表示已经匹配，黑色表示匹配失败）
但是我们发现这样匹配很浪费!
为什么这么说呢，我们看到第4步：
在第4步的时候，我们发现第3位上c与a不匹配，然后第五步的时候我们把B串向后移一位，再从第一个开始匹配。
这里就有一个对已知信息很大的浪费，因为根据前面的匹配结果，我们知道B串的前两位是ab，所以不管怎么移，都是不能和b匹配的,所以应该直接跳过对A串第二位的匹配，对于A串的第三位也是同理。
或许这这个例子还不够经典，我们再举一个。
A="abbaabbbabaa"
B="abbaaba"
在这个
延伸阅读
- ssh框架 2016-09-30
- 阿里移动安全 [无线安全]玩转无线电——不安全的蓝牙锁 2017-07-26
- 消息队列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 论文笔记【图片目标分割】 2017-07-26
- 词向量-LRWE模型-更好地识别反义词同义词 2017-07-26
- 从栈不平衡问题 理解 calling convention 2017-07-26
- php imagemagick 处理 图片剪切、压缩、合并、插入文本、背景色透明 2017-07-26
- Swift实现JSON转Model - HandyJSON使用讲解 2017-07-26
- 阿里移动安全 Android端恶意锁屏勒索应用分析 2017-07-26
- 集合结合数据结构来看看(二) 2017-07-26
学习是年轻人改变自己的最好方式