本题要求求出匹配子串长度恰好为x的位置,我们先对模式串做一遍kmp求next数组,对于匹配串做kmp并且记录以i为结尾的的cnt,假设以i为结尾的最大匹配长度为j,那么也有可能存在小于j并且也能匹配的最大长度,即j->ne[j],对于ne[j]也有ne[j]->ne[ne[j]],发现是从最大的不断累加到ne数组里直到为0,于是我们可以按照拓扑图,从大到小累加,最后输出x的时候需腰输出cnt[x]-cnt[x+1],即长度至少为x的个数减去长度至少为x+1的个数即为x的个数
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10,INF=1e8;
int n,m,Q,ne[N],cnt[N];
char s[N],q[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>Q;
cin>>s+1>>q+1;
for(int i=2,j=0;i<=m;i++)
{
while(j&&q[i]!=q[j+1]) j=ne[j];
if(q[i]==q[j+1]) j++;
ne[i]=j;
}
for(int i=1,j=0;i<=n;i++)
{
while(j&&s[i]!=q[j+1]) j=ne[j];
if(s[i]==q[j+1]) j++;
cnt[j]++;
}
for(int i=m;i>=1;i--) cnt[ne[i]]+=cnt[i];
while(Q--)
{
int x;
cin>>x;
cout<<cnt[x]-cnt[x+1]<<'\n';
}
return 0;
}