KMP算法
2022/1/10 14:03:53
本文主要是介绍KMP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
# 微信搜索公众号Corux,和我交朋友!
next[j]的含义是当主串中的第i个字符与模式中的第j个字符失配时,主串中的第i个字符应该与模式中哪个字符再比较,换句话说,next[j]表示当模式中的第j个字符与主串中相应的字符失配时,在模式中需重新和主串中该字符进行比较的字符的位置。
//主串:primary string,简记为prmr_str //模式串:pattern string,简记为pttn_str int kmp(string prmr_str, string pttn_str, int pos, int* next) { int i = pos, j = 0; while (i < prmr_str.length() && j < pttn_str.length()) { if (j == -1 || prmr_str[i] == prmr_str[j]) { ++i; ++j; } //j==-1时,第一个字符也不匹配,这时需要将模式串继续滑动 else j = next[j]; } return j == pttn_str.length() ? i - pttn_str.length() : -1; //返回-1表示没找到 }
KMP算法是在已知模式串的next数组的基础上执行的,那么如何求next数组呢?
我们考虑一般情况,找出next数组的递推关系,即通过next[j]得出next[j + 1].
假设当模式串匹配到j+1位置时与主串失配了,即模式串next[j + 1]位置与主串i位置的字符不匹配,但当前模式串中从0到j位置的字符与主串中对应位置的字符均匹配,此时next[j + 1]的求法:
int k = j; while ((k = next[k]) != -1 && pttn_str[j] != pttn_str[k]); next[j + 1] = k + 1;
则next数组整体的求法:
int* get_next(string s) { int len = s.length(); int* next = new int[len]; next[0] = -1; for (int j = 0; j != len - 1; ++j) { int k = j; while ((k = next[k]) + 1 && s[j] != s[k]); next[j + 1] = k + 1; } return next; }
另一种写法:
int* get_next(string s) { int len = s.length(); int* next = new int[len]; int i = 0, j = -1; next[0] = -1; while (i < len - 1) { if (j == -1 && s[i] == s[j]) { ++i; ++j; next[i] = j; //*** } else j = next[j]; } return next; }
在上述代码的星标位置考虑这样一种情况:模式串 i 位置的字符失配了,如果 j 位置的字符与 i 位置的字符相同,那么执行next[i] = j 之后仍然会失配,那么这步操作就相当于是一次无效的、多余的操作。为了避免这种情况,我们可增加一个条件判断:
if(s[i] != s[j]) next[i] = j; else next[i] = next[j];
因此求next数组的完整版代码如下所示:
int* get_next(string s) { int len = s.length(); int* next = new int[len]; int i = 0, j = -1; next[0] = -1; while (i < len - 1) { if (j != -1 && s[i] == s[j]) { ++i; ++j; if (s[i] != s[j]) next[i] = j; else next[i] = next[j]; } else j = next[j]; } return next; }
最终简化版:
int* get_next(string s) { int len = s.length(); int* next = new int[len]; int i = 0, j = -1; next[0] = -1; while (i < len - 1) j + 1 && s[i] != s[j] ? j = next[j] : next[i] = s[++i] != s[++j] ? j : next[j]; return next; }
这篇关于KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)