KMP算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了KMP算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1987字,纯文字阅读大概需要3分钟。
内容图文
![KMP算法](/upload/InfoBanner/zyjiaocheng/845/6974e6a2005345b99d02137de0f759c5.jpg)
概述
KMP(Knuth-Morris-Pratt)算法是一种用来解决字符串匹配问题的算法,时间复杂度为O(n+m),主要思想是当模式串与主串发生失配时,不必从头开始匹配,而是滑动到已经匹配的部分
next数组
在KMP算法中,next数组用来存储一段子串最大相等前后缀的长度加1,例如长度为i+1的字符串,它的最大相等前后缀分别为0~k和i-k~i,则next[i]=k
,这里k小于i。
问题在于如何去求next数组,遍历的话KMP算法就没什么意义了,但仔细观察就可以发现next[i]的值可以由已求出的next数组的值推导出
求next[i+1]只需考虑两种情况
- s[i+1] == next[i] + 1,则next[i+1] = next[i] + 1
- s[i+1] != next[i] = 1
对于第二种情况,我们需要一个变量j,我们令j=next[next[i]],如果s[i+1] == s[j+1],则next[i+1]=j+1。我认为整个KMP的精髓就在这里,这也是最难理解的一步。其实再看一下next数组的意义就知道了,这里s[0~j]肯定等于s[i-j~i],这里的一部分就是s[next[i]]所匹配出来的最大前后缀,如图所示
这样我们就可以轻松的求出next数组了
void getnext(char s[], int len) {
int j = -1, next[0] = -1;
for(int i = 0; i < n; i ++ ) {
while (j != -1 && s[i] != s[j+1]) {
j = next[j];
}
if (s[i] == s[j+1]) {
j++;
}
next[i] = j;
}
}
KMP算法的实现
命名变量i和j,i表示主串预匹配的下标,j表示模式串已匹配的下标,那么每次匹配过程无非有两种情况
- text[i] == pattern[j+1]
- text[i] != pattern[j+1]
对于第二种情况,我们不断地让j=next[j]
,直到text[i] == pattern[j+1]或者j等于-1
算法实现
bool KMP(char text[], char pattern[]) {
int n = strlen(text), m = strlen(pattern);
int next[m];
getnext(pattern, m);
int j = -1;
for (int i = 0; i < n; i ++ ) {
while (j != -1 && text[i] != pattern[j+1]) {
j = next[j];
}
if (text[i] == pattern[j+1]) {
j++;
}
if (j == m-1) {
return true;
}
}
return false;
}
算法优化
在while循环里每次回退找到j的过程可以更快一些,通过优化求解next数组的部分,因为如何已知s[j+1]==s[i+1],j肯定还要回退,我们直接让next数组存储每次适配时需要回到的那个j
void getnextval(char s[], int len) {
int j = -1, nextval[0] = -1;
for (int i = 0; i < len; i ++ ) {
while (j !=1 && s[j+1] != s[i]) {
j = nextval[i];
}
if (s[j+1] == s[i]) {
j++;
}
if (j == -1 || s[j+1] != s[i+1]) {
nextval[i] = j;
} else {
nextval[i] = nextval[j];
}
}
}
内容总结
以上是互联网集市为您收集整理的KMP算法全部内容,希望文章能够帮你解决KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。