柒葉灬 的博客

柒葉灬 的博客

kmp总结(个人笔记)

posted on 2018-12-27 22:04:58 | under 专题总结 |

$KMP$ 算法总结


$kmp$ 算法就是用来找 $string \ \ \ S$ 中存在多少个 $ string \ \ \ T $ ,时间复杂度为 $O(n+m)$

不在多叙述kmp算法,这不是算法学习(懒)


$kmp$ 算法中常常会有一个 $nxt$ 数组,维护的是最长的真前后缀匹配。

这是一段后来加的ps:

china 的 前缀:c , ch, chi, chin ,china

china 的真前缀:c , ch , chi, chin

模板代码:

void Getnxt(){
    nxt[1]=0;
    int j=0;
    for(int i=2;i<=lent;i++){
        while(j && t[i]!=t[j+1])
            j=nxt[j];
        if(t[i]==t[j+1])
            j++;
        nxt[i]=j;
    }
}

有了 $nxt$ 数组就可以查询了。

模板代码:

int Findans(){
    int j=0,ans=0;
    for(int i=1;i<=lens;i++){
        while(j && s[i]!=t[j+1])
            j=nxt[j];
        if(s[i]==t[j+1])
            j++;
        if(j==lent){
            ans++;
            j=nxt[j];
        }
    }
    return ans;
}

以上是基础


例题 专题G

题意:给一个字符串 $S$ ,问最多可以拆成多少个子串 $T$ ,使得 $S$ 由若干个 $T$ 组成,如: $S="ababab"\ \ , \ \ T="ab"$

思路:比如说题意中的 $S="ababab"$ ,

我们把 $nxt$ 全部打表写出来。

得到: $0 \ 0 \ 1 \ 2 \ 3 \ 4 $

惊喜发现 $ 1 \ 2 \ 3 \ 4 $ 很有规律

仔细分析:从第二个 $T$ 开始,接下来的 $nxt$ 数组全部都是递增的。(显然正确)

可以从最后一个 $nxt$ 数值里面推出 $T$ 的长度,判断一下是否可以整除就行了。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e6+5;
char str[maxn];
int n,nxt[maxn];
void Getnxt(){
    int j=0;
    nxt[1]=0;
    for(int i=2;i<=n;i++){
        while(j&&str[i]!=str[j+1])
            j=nxt[j];
        if(str[i]==str[j+1])
            j++;
        nxt[i]=j;
    }
}
int main(){
    while(scanf("%s",str+1),str[1]!='.'){
        n=strlen(str+1);
        Getnxt();
        int cnt=nxt[n];
        int len=n-cnt;
        if(cnt%len==0){
            printf("%d\n",cnt/len+1);
        }else puts("1");
    }
    return 0;
}           

例题 专题J

题意:给定一个字符串 $S$ ,其中有一些字符是位置的 $?$ ,再给一个字符串 $T$ ,问 $T$ 最多可以在 $S$ 出现多少次。

思路:需要用 $dp$ ,考虑遇到 $?$ 一定是要匹配的,(不匹配 = 后面不选)。但是匹配不一定是匹配当前这一位,可能往 $nxt$ 上走,所以来一个后缀最大值就可以了,倒着扫一遍,详细见代码。还有就是不是问号的情况,(套了个 $while$ 复杂度玄学,但可以优化预处理,因为过了就没有继续优化了)直接模拟就行了。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\t"<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+5;
template<class T>inline void tomax(T &a,T b){if(a<b)a=b;}
char s[maxn],t[maxn];
int ans,lens,lent;
int nxt[maxn],dp[maxn*105],tmp[maxn];
#define dp(i,j) dp[(i)*lent+(j)]
void Getnxt(){
    nxt[1]=0;
    int j=0;
    for(int i=2;i<=lent;i++){
        while(j&&t[i]!=t[j+1])
            j=nxt[j];
        if(t[i]==t[j+1])
            j++;
        nxt[i]=j;
    }
}
int main(){
    scanf("%s%s",s+1,t+1);
    lens=strlen(s+1);
    lent=strlen(t+1);
    if(lent>lens)return puts("0"),0;
    Getnxt();
    memset(dp,-63,sizeof(dp));
    dp(0,0)=0;
    for(int i=1;i<=lens;i++){
        if(s[i]=='?'){
            for(int j=0;j<lent;j++){
                tmp[j]=dp(i-1,j);
            }
            for(int j=lent-1;j>0;j--){
                tomax(tmp[nxt[j]],tmp[j]);
            }
            for(int j=1;j<lent;j++){
                dp(i,j)=tmp[j-1];
            }
            tomax(dp(i,nxt[lent]),tmp[lent-1]+1);
        }else {
            for(int j=0;j<lent;j++){
                if(dp(i-1,j)<0)continue;
                int k=j;
                while(k&&s[i]!=t[k+1])
                    k=nxt[k];
                if(s[i]==t[k+1])
                    k++;
                if(k==lent){
                    tomax(dp(i,nxt[lent]),dp(i-1,j)+1);
                }else {
                    tomax(dp(i,k),dp(i-1,j));
                }
            }
        }
    }
    for(int i=1;i<=lens;i++)
        for(int j=0;j<lent;j++)
            tomax(ans,dp(i,j));
    cout<<ans<<endl;
    return 0;
}

例题 专题K

题意:字符串可以被压成 数字+字符串的形式,比如说 $"aaaa"="4a"$ ,问给出的字符串 $S$ 最少被压成多少。(注意 $10$ 占 $2$ 个位置)。

思路:可以写 $O(n^2)$ 的 $dp$ ,所以只要求出压一个区间的最小代价就行了。就是上面 专题G 的升级版。

#include<bits/stdc++.h>
#define debug(x) cerr<<"DEBUG\t"<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=8e3+5;
int n,dp[maxn],dis[maxn][maxn];
char str[maxn];
int nxt[maxn];
void check(int s){
    nxt[s]=s-1;
    int j=s-1;
    for(int i=s+1;i<=n;i++){
        while(j>=s&&str[i]!=str[j+1])
            j=nxt[j];
        if(str[i]==str[j+1])
            j++;
        nxt[i]=j;
    }
    for(int i=s;i<=n;i++){
        int cnt=nxt[i]-(s-1);
        int len=i-s+1-cnt;
        if(cnt%len!=0){
            dis[s][i]=i-s+2;
        }else {
            int C=cnt/len+1;
            int S=len,tmp=0;
            while(C){tmp++;C/=10;}
            dis[s][i]=S+tmp;
        }
    }
}
int main(){
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i<=n;i++)
        check(i);
    memset(dp,63,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            dp[i]=min(dp[i],dp[j]+dis[j+1][i]);
    cout<<dp[n]<<endl;
    return 0;
}

$kmp$ 算法所解决的问题十分有限,就是可以维护一个最长相同前缀。

尤其要记住 $kmp$ 算法的核心:不做重复的比较。

不能干贪心的傻事, $n$ 给你 $5000$ ,你写了个 $O(n^2)$ ,您觉得合适吗