当前位置：首页 > news >正文

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

news 来源：原创 2024/5/20 5:58:25

【算法解析】
曾经在 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