KMP

相关

• 单个字符串匹配算法，对模式串预处理求出next数组，匹配时是模式串根据next数组进行跳转。
• KMP可用于匹配子串出现的位置，次数。
• 更常见的应用是根据next数组的性质，结合一些思维或者dp。
• \(next[i]\)即表示模式串前\(i\)个字符的最长前缀后缀相等的长度。
  • 也表示该最长相等后缀对应的前缀的末位置，i=next[i]就是表示跳到该前缀，常用。
  • i-nex[i]则表示前缀[0...i]的循环节大小(若有),i/(i-nex[i])就是表示循环节个数。

题目

CF471D MUH and Cube Walls

题意

有一面小墙和一面大墙，小墙可上升下降，问在大墙中能匹配多少个。

分析

很裸的可重叠KMP匹配子串个数，因为墙可升可降，即模式串可同加同减，显然不变的是差分数组，对差分数组进行kmp匹配即可，注意特判模式串长度为1的情况。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int a[N],b[N],n,m;
int nex[N];
void init(int s[],int n){
    int i=0,j=-1;
    nex[0]=-1;
    while(i<n){
        if(j==-1 || s[i]==s[j]){
            nex[++i]=++j;
        }else{
            j=nex[j];
        }
    }
}
int kmp(int s[],int n,int p[],int m){
    int i=0,j=0;
    init(p,m);
    int cnt=0;
    while(i<n && j<m){
        if(j==-1 || s[i]==p[j]){
            i++;
            j++;
        }else{
            j=nex[j];
        }
        if(j==m){
            cnt++;
            j=nex[j];
        }
    }
    return cnt;
}
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n-1;i++){
        a[i]=a[i+1]-a[i];
    }
    for(int i=0;i<m;i++){
        scanf("%d",&b[i]);
    }
    for(int i=0;i<m-1;i++){
        b[i]=b[i+1]-b[i];
    }
    int ans=kmp(a,n-1,b,m-1);
    if(m==1){
        //注意特判
        ans=n;
    }
    printf("%d\n",ans);
    return 0;
}

hdu3336 Count the string

题意

近十年前的一道经典题，给定字符串，求所有前缀作为子串出现的次数之和。

分析

根据next数组的性质，我们从后往前枚举前缀，显然当\(s[0...i-1]\)出现一次时，\(s[0...nex[i]-1]\)也出现了一次，因此定义dp状态为\(dp[i]\)表示长度为i的前缀出现的次数，显然转移式为\(dp[i]+=1\)，且\(dp[nex[i]]+=dp[i]\)。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
const int mod=10007;
int T,n;
char s[N];
int nex[N];
int dp[N];
void init(char *s,int n){
    int i=0,j=-1;
    nex[0]=-1;
    while(i<n){
        if(j==-1 || s[i]==s[j]){
            nex[++i]=++j;
        }else{
            j=nex[j];
        }
    }
}
void solve(int n){
    for(int i=n;i>=1;i--){
        dp[i]++;
        dp[i]%=mod;
        dp[nex[i]]+=dp[i];
        dp[nex[i]]%=mod;
    }
}
int main(void){
//    freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        scanf("%s",s);
        init(s,n);
        solve(n);
        int ans=0;
        for(int i=1;i<=n;i++){
            ans=(ans+dp[i])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}