传送门

题意是说给定长度为n的字符串A，长度为m的字符串B，q个询问

每次询问有A的所有后缀里有多少个使得与B的前缀匹配长度恰好为K

在对A字符串做匹配的时候，本来 f[i] = j 表示的是A中以A[i]结尾的后缀与B的前缀的最大匹配长度。现在要改一下定义。f[x]表示匹配长度至少为x的有多少个位置。

当A中以A[i]结尾的字符串与B的最大匹配长度为j的时候，证明产生了一个匹配长度至少为j的后缀，但是不一定是恰好为j，因为此时的A[i]结尾字串并不是A数组的后缀。然后需要发现：匹配长度至少为next[j]的后缀的数量也增加了。

于是f函数的各个函数值之间是拓扑的关系。f[k] = \sum\limits_{next[j]=k} f[j]

于是匹配长度恰好为x的数量就是f[ x ] – f[ x + 1 ]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int n, m, q;
char a[maxn], b[maxn];
int ne[maxn], f[maxn];
int main()
{
    cin >> n >> m >> q;
    cin >> a + 1 >> b + 1;
    ne[1] = 0;
    for(int i =2, j = 0; i <= m; i++)
    {
        while(j > 0 && b[i] != b[j + 1]) j = ne[j];
        if(b[i] == b[j + 1]) j++;
        ne[i] = j;
    }
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j > 0 && (j == m || a[i] != b[j + 1])) j = ne[j];
        if(a[i] == b[j + 1]) j++;
        f[j]++;
    }
    for(int i = m; i; i--) f[ne[i]] += f[i];
    for(int i = 1; i <= q; i++)
    {
        int k; scanf("%d", &k);
        printf("%d\n", f[k] - f[k + 1]);
    }
}

然而有无脑二分的做法。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
typedef unsigned long long ull;
int n, m, q;
char a[maxn], b[maxn];
int f[maxn];
ull h1[maxn], h2[maxn], p[maxn], base = 131;
ull get(ull h[], int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
bool gao(int x, int k)
{
    return get(h2, 1, 1 + k) == get(h1, x, x + k);
}
int main()
{
    cin >> n >> m >> q;
    cin >> a + 1 >> b + 1;
    p[0] = 1;
    for(int i = 1; i <= max(n, m); i++) p[i] = p[i - 1] * base;
    for(int i = 1; i <= n; i++) h1[i] = h1[i - 1] * base + a[i] - 'a' + 1;
    for(int i = 1; i <= m; i++) h2[i] = h2[i - 1] * base + b[i] - 'a' + 1;
    for(int i = 1; i <= n; i++)
    {
        int l = 0, r = min(n, m);
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(gao(i, mid)) l = mid + 1;
            else r = mid;
        }
        f[l]++;
    }
    for(int i = 1; i <= q; i++)
    {
        int k; scanf("%d", &k);
        printf("%d\n", f[k]);
    }
}