李春葆、严蔚敏关于KMP算法的next数组值差1

87 阅读 0 评论 58 点赞

我是靠谱客的博主清爽金鱼，最近开发中收集的这篇文章主要介绍李春葆、严蔚敏关于KMP算法的next数组值差1，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【算法解析】
曾经在 https://blog.csdn.net/hnjzsyjyj/article/details/127086502 提到，在KMP算法的众多实现中，有多种定义next数组的方式。所以在使用和查看别人代码时，要特别注意KMP算法的next数组的定义，以免发生混淆。如：
• 严蔚敏《数据结构》将模式串下标从1开始计数，故定义next[1]=0，next[2]=1；
• 李春葆《数据结构》将模式串下标从0开始计数，故定义next[0]=-1，next[1]=0。

由于字符串的下标在C++中从0开始，因此在利用C++进行KMP算法的设计中，将next数组下标从0开始考虑，是很自然的事情。据此，建议选择李春葆《数据结构》中关于模式串下标的定义，即从0开始考虑，据此可定义next[0]=-1，next[1]=0。之后，按照“（1）若第i-1位的字符与第j位的字符相等，则next[i]=j+1；（2）若直到第0位依然没有字符与第i-1位的字符相等，则next[i]=0”构建next数组。

通过观察，发现“李春葆、严蔚敏关于KMP算法的next数组值差1”。这就给出了启发。即：
如果李春葆定义法的next数组值（以“-1 0 ”开头），利用 cout<<next[i]; 输出。
那么严蔚敏定义法的next数组值（以“0 1”开头），便可利用 cout<<next[i]+1; 输出。
也就是说，仅需修改一条语句，便可复用代码，实现李春葆定义法、严蔚敏定义法中next数组值的输出。

【输出李春葆定义法next数组值的算法代码】

#include<iostream>
using namespace std;
const int maxn=100;
int ne[maxn];
void getNext(string s) {
int len=s.length();
int i=0, j=-1;
ne[0]=-1;
while(i<len) {
if(j==-1 || s[i]==s[j]) {
ne[++i]=++j;
} else j=ne[j];
}
}
int main() {
string T;
getline(cin,T);
getNext(T);
for(int i=0; i<T.length(); i++) {
cout<<ne[i]<<" ";
}
return 0;
}
/*
input: ababaaababaa
output: -1 0 0 1 2 3 1 1 2 3 4 5
*/

【输出严蔚敏定义法next数组值的算法代码】

#include<iostream>
using namespace std;
const int maxn=100;
int ne[maxn];
void getNext(string s) {
int len=s.length();
int i=0, j=-1;
ne[0]=-1;
while(i<len) {
if(j==-1 || s[i]==s[j]) {
ne[++i]=++j;
} else j=ne[j];
}
}
int main() {
string T;
getline(cin,T);
getNext(T);
for(int i=0; i<T.length(); i++) {
cout<<ne[i]+1<<" ";
}
return 0;
}
/*
input: ababaaababaa
output: 0 1 1 2 3 4 2 2 3 4 5 6
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/127086502
https://blog.csdn.net/hnjzsyjyj/article/details/127105603
https://blog.csdn.net/hnjzsyjyj/article/details/127112363