B 题题解

B 题

这里下标从 0 开始

考虑KMP找到模式串在文本串中的第一个位置。

假设在文本串中区间[i,j]能匹配。

根据乘法原理，那么每次有(i+1)*(n-j)。但是有重复的部分。

注意到每一次都把一类左端点的贡献都算了，所以记录一个变量ss表示当前已经计算过多少个左端点的贡献，在下一次计算时把可以得到的左端点个数减去ss即可。即为 (i+1-ss)*(n-j)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=0,ch=getchar();
    while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
    return f?-x:x;
}
const int MAX=1e7+5;
string s,p;
int n,nex[MAX],ans,ss;
inline void init(){
    nex[0]=-1;
    int j=0,k=-1;
    while(j<p.length()){
        if(k==-1||p[j]==p[k])++j,++k,nex[j]=k;
        else k=nex[k];
    }    
}
inline void KMP(){
    int i=0,j=0;
    while(i<s.length()){
        if(j==-1||s[i]==p[j])++i,++j;
        else j=nex[j];
        if(j==p.length()){
            ans+=(i-p.length()+1-ss)*(s.length()-i+1);
            ss=i-p.length()+1;
        }
    }
}
int t,k;
signed main(){
    n=read(),k=read();
    cin>>s>>p;
    init();
    KMP();
    printf("%lld\n",ans);
    return 0;
}