题目描述

给定两个字符串 $A,B$ 以及若干询问，每次询问给出一个整数 $x$，需要回答 $A$ 中有多少个位置，满足“字符串 $A$ 从该位置开始的后缀子串”与 $B$ 匹配的长度恰好为 $x$。

算法1：哈希+二分/哈希+倍增

用哈希搭配二分、倍增等带一个 $log$ 的算法更新 $A$ 串中每个子串与 $B$ 串的匹配长度，$O(1)$ 回答每个询问。

总复杂度 $O(NlogN+Q).$

算法2：KMP

先将 $A$、$B$ 两串用 KMP 算法进行匹配，再利用 KMP 算法性质 $O(1)$ 回答询问。

总复杂度 $O(N+M+Q).$

以上两种做法其他题解已详细讲解，在此不再赘述。

算法3：$Z$ 函数

蓝书上并没有对 $Z$ 函数(国内流行叫法为扩展 KMP)进行讲解，但个人认为这是一种相当方便的算法。NOIP2020 T2 就可以用作 $Z$ 函数的绝佳练习题。

$Z$ 函数可以在 $O(N)$ 时间内求出给定字符串每个后缀与该字符串前缀的最大匹配长度，类似地，也可以在 $O(N+M)$ 的时间内求出字符串 $A$ 每个后缀与字符串 $B$ 的最大匹配长度。
关于 $Z$ 函数的计算方法，本文不进行探讨。有兴趣的读者可参阅 OI-Wiki$^{[1]}$ 上的讲解。

具体地，实现这一点有两种方法。

方法一：构建字符串 $A+@+B$，其中 $@$ 为任意一个既没有出现在 $A$ 串中，也没有出现在 $B$ 串中的字符，并对构造出来的字符串求 $Z$ 函数。

方法二：先对串 $B$ 进行 $Z$ 函数自匹配，再利用求出来的 $Z$ 函数进行 $A$ 串与 $B$ 串的匹配。

方法二无需进行字符串连接，为实际解题时被普遍使用的做法。

容易发现，只要写一个 $Z$ 函数模板即可通过本题。

由于该解法不涉及算法的复杂应用，个人给本题评出的难度等级为“简单”。

C++代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int ask[200010],cnt[200010],n,m,q,len1,len2,z[200010],p[200010];
char a[200010],b[200010];
int Min(int a,int b){return a<b?a:b;}
int Max(int a,int b){return a>b?a:b;}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(int l=0,r=0,i=2;i<=m;i++){//求B串Z函数
        if(i<=r)z[i]=Min(z[i-l+1],r-i+1);
        while(z[i]<m&&i+z[i]<=m&&b[z[i]+1]==b[i+z[i]])z[i]++;
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }
    for(int l=0,r=0,i=1;i<=n;i++){//利用B的Z函数匹配A、B两串
        if(i<=r)p[i]=Min(z[i-l+1],r-i+1);
        while(p[i]<m&&i+p[i]<=n&&b[p[i]+1]==a[i+p[i]])p[i]++;
        if(i+p[i]-1>r)l=i,r=i+p[i]-1;
        cnt[p[i]]++;
    }
    for(int i=1;i<=q;i++)scanf("%d",ask+i);
    for(int i=1;i<=q;i++)printf("%d\n",cnt[ask[i]]);
}

参考文献

$[1]$ OI-Wiki 上关于 $Z$ 函数的讲解