笔记 - 算法 - 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. 附: 参考文档
https://www.cnblogs.com/yjiyjige/p/3263858.html
笔记 - 算法 - KMP 算法
来源: http://www.bubuko.com/infodetail-2770309.html