题解 P3375 【模板】KMP字符串匹配

· · 个人记录

前言：虽然KMP板子题解已经满了，但写题解本来就不只是为了功利的估值，更是为了自己对该题有更深的理解，所以便有了此篇题解。

1.题意简述

给定两个字符串s_1和s_2，按从小到大的顺序输出s_2在s_1中所有出现的起始位置,并在最后一行输出kmp数组的值。

2.解题思路

这就没什么好说的，裸的KMP，打板子即可。

3.代码

这题有两种写法，char数组和string 1.string

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define ll long long
#define gc getchar
#define int long long
#define R register
using namespace std;
//---------------------初始函数-------------------------------
il int read(){
    R int x=0;R bool f=0;R char ch=gc();
    while(!isdigit(ch)) {f|=ch=='-';ch=gc();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    return f?-x:x;
}

il int max(int a,int b) {return a>b?a:b;}

il int min(int a,int b) {return a<b?a:b;}

//---------------------初始函数-------------------------------

const int MAXN=1e6+10;
string s1,s2;

//-------------------------KMP算法---------------------------
int nxt[MAXN];
void getnext(string t){
    int j=0,k=-1;
    nxt[0]=-1;
    while(j<t.size()){
        if(k==-1||t[j]==t[k]) nxt[++j]=++k;
        //1.当k=-1时，肯定到顶了，不能再回溯，所以直接赋值
        //2.当t[j]==t[k]时，这个下标的nxt值就是上一个下标的值加1
        else k=nxt[k];//如果还没有找到，就返回上一个可回溯的下标再找
    }
}

void KMP(string s,string t){
    int i=0,j=0;
    while(i<s.size()){
        if(j==-1||s[i]==t[j]){++i;++j;}
        //1.当j=-1时，说明到了边界，把文本串的指针加1,再重新开始新一轮匹配
        //2.当s[i]==t[j]时，说明匹配到了，那就指针往后移，看下一位能否匹配
        else j=nxt[j];//如果没有到边界又没有匹配到，就回溯看能否重新匹配
        if(j==t.size()){printf("%lld\n",i-t.size()+1);j=nxt[j];}
        //当j==t.size()时，说明已经完全匹配了，输出答案，并回溯匹配其他位置上的合法答案
        //对输出结果的解释:i表示到下标为i的位置时两串完全匹配，减去（t.size()-1）就是减去模式串的长度，结果就是匹配的起始位置
    }   
}

//-------------------------KMP算法---------------------------

signed main(){
    cin>>s1>>s2;
    getnext(s2);
    KMP(s1,s2);
    for(R int i=1;i<=s2.size();++i) printf("%lld ",nxt[i]);
    return 0;
}

2.char数组

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define ll long long
#define gc getchar
#define int long long
#define R register
using namespace std;
//---------------------初始函数-------------------------------
il int read(){
    R int x=0;R bool f=0;R char ch=gc();
    while(!isdigit(ch)) {f|=ch=='-';ch=gc();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    return f?-x:x;
}

il int max(int a,int b) {return a>b?a:b;}

il int min(int a,int b) {return a<b?a:b;}

//---------------------初始函数-------------------------------

const int MAXN=1e6+10;
char s1[MAXN],s2[MAXN];
int kmp[MAXN];

signed main(){
    scanf("%s%s",s1+1,s2+1);
    //细节：s1+1表示从下标为一的位置开始读入，方便之后的操作
    int lens1=strlen(s1+1),lens2=strlen(s2+1);
    //因为char不像string一样有很多自带函数，所以要用<cstring>库中的函数求长度
    kmp[0]=kmp[1]=0;//初始化
    for(R int j=2,k=0;j<=lens2;++j){
        while(k&&s2[j]!=s2[k+1]) k=kmp[k];
        //当k>0且s2[j]!=s2[k+1]时，说明既没有到边界又没有匹配到，就回溯看能否重新匹配
        if(s2[j]==s2[k+1]) ++k;
        //由上面的while循环可知，现在的k一定是匹配的，所以我们只需要判断这一位能否比上一位多匹配一个字符
        kmp[j]=k;//赋值这一位最多能匹配的字符
    }
    for(R int j=1,k=0;j<=lens1;++j){
        while(k&&s1[j]!=s2[k+1]) k=kmp[k];
        //当k>0且s2[j]!=s2[k+1]时，说明既没有到边界又没有匹配到，就回溯看能否重新匹配
        if(s1[j]==s2[k+1]) ++k;
        //由上面的while循环可知，现在的k一定是匹配的，所以我们只需要判断这一位能否比上一位多匹配一个字符
        if(k==lens2){printf("%lld\n",j-lens2+1);k=kmp[k];}
        //当k==lens2时，说明已经完全匹配了，输出答案，并回溯匹配其他位置上的合法答案
        //对输出结果的解释:j表示到下标为j的位置时两串完全匹配，减去（lens2-1）就是减去模式串的长度，结果就是匹配的起始位置        
    }
    for(R int i=1;i<=lens2;++i) printf("%lld ",kmp[i]);
    return 0;
}