首页 > 代码库 > KMP算法
KMP算法
看了半天理解了思想，但是还是看不懂代码。下面这篇写的不错，推荐一下。
http://www.tuicool.com/articles/e2Qbyyf
怎样得到 next 函数
相当于字符串 T 自身做一次匹配。（下标从 1 开始）
void getnext() {
next[1] = 0;
for(int i = 2; i <= n; i++) {
int j = next[i - 1];
while(t[j + 1] != t[i] && j > 0) {
j = next[j];
}
if(t[j + 1] == t[i]) {
next[i] = j + 1;
} else {
next[i] = 0;
}
}
}
模式匹配
字符串 S 与字符串 T 做一次匹配。
int kmp() {
int j = 0;
for(int i = 1; i <= m; i++){
while(t[j + 1] != s[i] && j > 0) {
j = next[j];
}
if(t[j + 1] == s[i]) {
j++;
}
if(j >= n) {
return i - n + 1;
}
}
return 0;
}
总的时间复杂度是 O(N+M) 即线性的。
KMP算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。