湘潭做网站 联系磐石网络,泌阳专业网站建设,二手交易平台的网站怎么做,小型网站网站建设需要概念
KMP算法#xff0c;全称Knuth Morris Pratt算法 。文章大部分内容出自《数据结构与算法之美》
核心思想
假设主串是a#xff0c;模式串是b
在模式串与主串匹配的过程中#xff0c;当遇到不可匹配的字符的时候#xff0c;对已经对比过的字符#xff0c;是否能找到…概念
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 cnext数组的计算
暴力计算方法
暴力求解子串效率低 把所有后缀子串从长到短找出来依次看能否匹配前缀
类动态规划方法(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表示模式串长度
