笔记-算法-KMP算法
笔记-算法-KMP算法
1. KMP算法
KMP算法是一种改进的字符串匹配算法,KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
1.1. 基本思想
设主串(m)为:BBC ABCDAB ABCDABCDABDE
模式串(p)为:ABCDABD
1.首先,p首位与m第1位匹配,结果为否,搜索后移1位;
2.至P首位与m第4位匹配,后续5位也匹配,但第6位不匹配;搜索后移;
3.如果搜索仍后移1位,则是常规穷举算法,KMP算法的想法是,设法利用前5位不匹配这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。
4.怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。
5.已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:
移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于4,所以将搜索词向后移动4位。
6.接下来按部就班的重复直到找到全匹配或搜索至尾端结束搜索;
7.匹配表:
匹配表是“前缀”和“后缀”的最长共有元素的长度。以ABCDABD为例:
- "A"的前缀和后缀都为空集,共有元素的长度为0;
- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
- "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。
8."部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置
1.2. 代码实现
def get_next(p):
p_len = len(p)
i, j = 0, -1
next[0] = -1
while i < p_len-1:
if j == -1 or p[i] == p[j]:
i += 1
j += 1
next[i] = j
else:
j = next[j]
return next
def kmp(s,p):
slen, plen = len(s), len(p)
if slen >= plen:
i, j = 0, 0
next = getnext(p)
while i < slen:
if j == -1 or s[i] == p[j]:
i += 1
j += 1
else:
j = next[j]
if j == plen:
return j - plen
return -1
2. 附:参考文档
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://www.cnblogs.com/yjiyjige/p/3263858.html
最新文章
- Linux程序包管理之rpm
- Android的编码规范
- 干货——myeclipse快捷键
- 关于echart横轴颜色 纵轴颜色 以及文本颜色的修改
- 优雅绝妙的Javascript跨域问题解决方案
- jmeter学习预热
- normalization归一化
- plsql基本语法(
- LVS结合keepalive
- maven的依赖特性
- MIPS汇编指令集
- SQL Server表关联
- iOS设置图片名称、启动图片、防止TabBar图片和文字渲染
- 【转】Linux下从TCP状态机,三次握手判断DDOS攻击
- apache配置禁止访问某些文件/目录
- [翻译] CBStoreHouseRefreshControl
- rundeck
- 接口测试(概念、Postman、SoapUI、jmeter)
- (转)java中Executor、ExecutorService、ThreadPoolExecutor介绍
- Redis2.8配置文件详解(转)
热门文章
- Likely root cause: java.lang.IllegalStateException: jar hell!
- 使用Pycharm开发python下django框架项目生成的文件解释
- 什么是Spring
- ubuntu命令收集
- 链接文字<;a>;保持原有的字体颜色
- 使用HTML5 canvas做地图(1)基础知识
- Markdown引用图片,且不使用网上链接的解决方法
- N 叉树的层序遍历
- 不得不承认pretty-midi很好用,以及一些简单的上手
- 小记:vue 及 react 的工程项目入口小结及 webpack 配置多页面应用参考