大一菜鸟，即将大二，依旧菜鸟一只QAQ

最近在中国大学慕课上看数据结构的课程，我看的是西安邮电大学的数据结构与算法课，kmp算法出现在“串”那一章节

具体内容我就不细讲了，大家可以去看一下。老师讲得还是很明白的。

  • next数组的实现

注意：网上的课程中默认字符串的下标从1开始

实现思路：

比如j=4时next[4]=2，即下次比较时从第二个字符开始比较（下标从1开始），第一个0指下次比较时从第一个字符开始

代码实现：（注意下标从1开始）

int main() {
    char s1[maxn],s2[maxn];//s1是文本串，s2是模式串
    int next[maxn];
    scanf("%s",s2+1);//从1开始读或者写成cin>>s2+1;
    int i,j=1,k=0,len=strlen(s2+1);
    next[1]=0;
    while(j<len)
    {
        if(k==0||s2[j]==s2[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
    for(i=1;i<=len;i++)
        cout<<next[i]<<" ";
    return 0;
}

以ababcabaababb为例，输出如下：

  • kmp算法的实现：

思路：

实现代码：


int main() {
    char s1[maxn],s2[maxn];//s1是文本串，s2是模式串
    int next[maxn];
    scanf("%s%s",s1+1,s2+1);
    int i=1,j=1,len1=strlen(s1+1),len2=strlen(s2+1);//i指向文本串，j指向模式串，从文本串
                                                //的第i位开始查找
    while(i<=len1&&j<=len2)
    {
        if(j==0||s1[i]==s2[j])
        {
            i++;
            j++;
        }
        else j=next[j];
    }
    if(j>len2) cout<<i-len2<<endl;//返回完全匹配的初始位置
    else cout<<"-1"<<endl;
    return 0;
}

  • 实现kmp算法的完整代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define maxn 1000000
using namespace std;
int main() {
    char s1[maxn],s2[maxn];//s1是文本串，s2是模式串
    int next[maxn];
    scanf("%s%s",s1+1,s2+1);
    int i=1,j=1,k=0,len1=strlen(s1+1),len2=strlen(s2+1);//i指向文本串，j指向模式串
    next[1]=0;
    while(j<len2)//因为内层油j++，所以j最大为len2-1，等于len2时就退出
    {
        if(k==0||s2[j]==s2[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
    i=1,j=1;//i文本串 j模式串
    while(i<=len1&&j<=len2)
    {
        if(j==0||s1[i]==s2[j])
        {
            i++;
            j++;
        }
        else j=next[j];
    }
    if(j>len2) cout<<i-len2<<endl;//返回完全匹配的初始位置
    else cout<<"-1"<<endl;
    return 0;
}

输出结果：

ababcabaababb
abaa
0 1 1 2 
6

但是，思考在计算next数组时，如果s2=aaaaab，s2对应的next数组为0 1 2 3 4 5

如果在比较第4位时不同需要进行如图操作：

实际上我们知道，模式串第四位之前的字母也都是a，所以在按之前的操作执行的话肯定都是不等的，最后还是重新要从模式串的第一位比较，同时指向文本串的i右移一位，所以这个时候直接执行“从模式串的第一位比较，同时指向文本串的i右移一位”这个操作即可，如下图：

黑色框内的步骤无需执行，直接执行橙色圈内的操作即可，所以需要对之前的next数组，进行优化，我们称它为nextval数组，用nextval数组来代替next数组

  • nextval数组的实现

实现代码：

#include <iostream>
#include <cstring>
using namespace std;
#define maxn 100000//如果数组定义在main内，不能开太大
int main()
{
    char s1[maxn],s2[maxn];//s1文本串，s2模式串
    scanf("%s",s2+1);
    int i,j,k,len1=strlen(s1+1),len2=strlen(s2+1);
    int next[maxn],nextval[maxn];
    next[1]=0;
    j=1,k=0;
    while(j<len2)
    {
        if(k==0||s2[j]==s2[k])
        {
            k++;
            j++;
            next[j]=k;
        }
        else k=next[k];
    }
    for(i=1;i<=len2;i++)
        cout<<next[i]<<" ";
    cout<<endl;
    j=2;k=0;
    while(j<=len2)
    {
        k=next[j];
        if(s2[j]==s2[k])
            nextval[j]=nextval[k];
        else nextval[j]=next[j];
        j++;
    }
    for(i=1;i<=len2;i++)
        cout<<nextval[i]<<" ";
    cout<<endl;
    return 0;
}
aaaaab
0 1 2 3 4 5 
0 0 0 0 0 5

  • 优化后的kmp算法的完整代码为：（终极版）

#include <iostream>
#include <cstring>
using namespace std;
#define maxn 100000//如果数组定义在main内，不能开太大
int main()
{
    char s1[maxn],s2[maxn];//s1文本串，s2模式串
    scanf("%s%s",s1+1,s2+1);
    int i,j,k,len1=strlen(s1+1),len2=strlen(s2+1);
    int next[maxn],nextval[maxn];
    next[1]=0;
    j=1,k=0;
    while(j<len2)
    {
        if(k==0||s2[j]==s2[k])
        {
            k++;
            j++;
            next[j]=k;
        }
        else k=next[k];
    }
    j=2;k=0;
    while(j<=len2)
    {
        k=next[j];
        if(s2[j]==s2[k])
            nextval[j]=nextval[k];
        else nextval[j]=next[j];
        j++;
    }
    i=1;j=1;//i指文本串，j指模式串
    while(i<=len1&&j<=len2)
    {
        if(j==0||s1[i]==s2[j])
        {
            i++;
            j++;
        }
        else j=nextval[j];
    }
    if(j>len2) cout<<i-len2<<endl;
    else cout<<"-1"<<endl;
    return 0;
}

输出样例：

ababcabaababb
abaa
6
aaaaab
ab
5

最后一个代码才是完整的kmp代码，至此，查找（匹配）子串，并返回相匹配时第一个字母出现的位置的知识点就都总结完了

还是不懂的盆友可以看我在博客开头推荐的视频或者和百度哦～我也只是微微懂一些罢了哈哈哈

欢迎交流讨论，非诚勿扰哦～邮箱：1308989543@qq.com