南通企业网站建设公司大连三大网络推广网站
概念
KMP算法，全称Knuth Morris Pratt算法 。文章大部分内容出自《数据结构与算法之美》
核心思想
假设主串是a，模式串是b
在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，对已经对比过的字符，是否能找到一种规律，将模式串一次性滑动多位，跳过那些肯定不会匹配的情况？
这里可以类比一下，在模式串和主串匹配的过程中,把不能匹配的那个字符仍然叫做坏字符，把已经匹配的那段字符串叫做好前缀
当遇到坏字符的时候，就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较
KMP目的
只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀匹的前缀子串匹配
假设最长的可匹配的那部分前缀子串{v}, 长度为k
可以把模式串一次性往后滑动j - k位，相当于，每次遇到坏字符的时候，就把j 更新为k。i不变。然后比较
最长可匹配后缀子串 && 最长可匹配前缀子串
把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串
对应的前缀子串，叫作最长可匹配前缀子串
为什么求最长可匹配子串前缀和后缀子串，为什么不涉及主串，只需通过模式串就能求解？
以上图所示，好前缀的定义是主串和模式串匹配的部分
所以好后缀的最长可匹配子串必然会落到模式串中，所以用模式串求最长可匹配的前缀和后缀子串
失效函数(next 数组)
数组的下标是每个前缀结尾字符下标，数组的值是这个
前缀的最长可以匹配前缀子串的结尾字符下标
例子：ababacd
- 前缀列表访问顺序：从右到左
- 后缀列表访问顺序：从左到右
过程
1. a: 无匹配，下标为-1
2. ab: 无匹配，下标为-1
3. aba: 匹配1个字符。下标为0前缀： a ab后缀： ba a
4. abab，匹配2个字符，下标为1前缀：a ab aba后缀：bab ab b
5. ababa，匹配3个字符，下标为2前缀：a ab aba abab后缀：baba aba ab a
6. ababac，无匹配，下标为-1前缀：a ab aba abab ababa后缀：babac abac bac ac c
7. ababacd，无匹配，下标为-1前缀：a ab aba abab ababa ababac后缀：babacd abacd bacd acd cd c
next数组的计算
暴力计算方法
暴力求解子串，效率低
把所有后缀子串从长到短找出来，依次看能否匹配前缀
类动态规划方法(k：最长前后缀子串)
若p[k] == p[i]
如果 next[i - 1] = k - 1，那么子串 b[0, k - 1] 是 b[0, i - 1]最长可匹配前缀子串
如果子串 b[0, k - 1] 的下一个字符 b[k]，与 b[0, i -1 ]的下一个字符 b[i] 匹配，那子串 b[0, k]就是 b[0, i]的最长可匹配前缀子串
若p[k] ≠ p[i]
假设最长可匹配前缀 k
如果 p[k] ≠ p[i]。则需要次最大匹配前缀 p[next[k]].
如果 p[next[k]] ≠ p[i]. 则需要次次最大匹配前缀。直到匹配成功，或者匹配失败
代码地址
数据结构和算法
时间复杂度
构建next数组
void getNext(char *p, int p_len, int *next) {next[0] = -1;int k = -1;int i;for (i = 1; i < p_len; ++i) {while (k != -1 && p[k + 1] != p[i]) {k = next[k];}if (p[k + 1] == p[i]) {++k;}next[i] = k;}}
i 从1开始一直增加到p_len,而k并不是每次for循环都增加，所以，k累积增加的值肯定小于 p_len
而while循环中的 k = next[k],实际上是在减小k的值，k累积都没有增加超过p_len.所以while循环总数也不会超过p_len
这部分时间复杂度: O(p_len)
借助next数组匹配
int kmp(char *s, int s_len, char *p, int p_len) {int next[p_len];getNext(p, p_len, next);int j = 0;int i;for (i = 0; i < s_len; ++i) {while (j > 0 && s[i] != p[j]) { // 一直找到s[i] 和 p[j]j = next[j - 1] + 1;}if (s[i] == p[j]) ++j;if (j == p_len) { // 找到匹配模式串return i - p_len + 1;}}return -1;
}
i 从0循环增加到 s_len - 1, j的增长量不可能超过i，所以肯定小于s_len
而while 循环中的那条 j = next[j - 1] + 1; 不会让 j增长
所以，这部分的时间复杂度为O(s_len)
总时间复杂度: O(s_len + p_len)
空间复杂度
KMP只需要一个额外的next数组，数组的大小跟模式串相同
空间复杂度:O(p_len), p_len表示模式串长度