大一菜鸟,即将大二,依旧菜鸟一只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