题目描述

阿轩在纸上写了两个字符串，分别记为 $A$ 和 $B$。

利用在数据结构与算法课上学到的知识，他很容易地求出了“字符串 $A$ 从任意位置开始的后缀子串”与“字符串 $B$ ”匹配的长度。

不过阿轩是一个勤学好问的同学，他向你提出了 $Q$ 个问题：

在每个问题中，他给定你一个整数 $x$，请你告诉他有多少个位置，满足“字符串 $A$ 从该位置开始的后缀子串”与 $B$ 匹配的长度恰好为 $x$。

例如：$A =$ aabcde，$B =$ ab，则 $A$ 有 aabcde、abcde、bcde、cde、de、e 这 $6$ 个后缀子串，它们与 $B=$ ab 的匹配长度分别是 $1$、$2$、$0$、$0$、$0$、$0$。

因此 $A$ 有 $4$ 个位置与 $B$ 的匹配长度恰好为 $0$，有 $1$ 个位置的匹配长度恰好为 $1$，有 $1$ 个位置的匹配长度恰好为 $2$。

输入格式

第一行输入三个整数 $N,M,Q$，分别表示 $A$ 串长度、$B$ 串长度、问题个数。

第二行输入字符串 $A$，第三行输入字符串 $B$。

接下来 $Q$ 行每行输入 $1$ 个整数 $x$，表示一个问题。

输出格式

输出共 $Q$ 行，依次表示每个问题的答案。

数据范围

$1 \leq N,M,Q,x \leq 200000$

输入样例：

6 2 5
aabcde
ab
0
1
2
3
4

输出样例：

4
1
1
0
0

算法1

(哈希) $\mathcal O(N \log N + M + Q)$

先分别求出 $A$ 与 $B$ 的哈希数组，对于 $a$ 中的每一个后缀，二分求一下能匹配的 $B$ 的最大前缀即可。
详见代码注释

时间复杂度

求出 $A$ 的哈希数组，时间复杂度是 $\mathcal O(N)$
求出 $B$ 的哈希数组，时间复杂度是 $\mathcal O(M)$
一共要二分 $N$ 次，每次二分的时间复杂度是 $\mathcal O(\log N)$，所以二分的总时间复杂度是 $\mathcal O(N \log N)$
要处理 $Q$ 次询问，每次询问的时间复杂度是 $\mathcal O(1)$，处理所有询问的时间复杂度就是 $\mathcal O(Q)$
所以总的时间复杂度为 $\mathcal O(N \log N + M + Q)$

C++ 代码

#include <stdio.h>
#include <string.h>

typedef unsigned long long ULL;
const int N = 200005;
const ULL P = 131;

int n, m, q;                    // 题目中 N, M, Q
char A[N], B[N];                // 题目中 A, B
ULL hash_A[N], hash_B[N], p[N]; // hash_A, hash_B 分别存 A, B 的哈希值。p 存 P 的 i 次幂，用于求出每个子串的哈希值。
int cnt[N];                     // 二分预处理的 A 中每个后缀与 B 匹配的最长长度，存入 cnt

ULL get(ULL h[], int l, int r)  // 返回 h 中 [l, r] 的哈希值
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d%d\n", &n, &m, &q);
    scanf("%s\n%s", A + 1, B + 1); // 由于要处理哈希，从 1 开始输入会方便一些
    p[0] = 1;                      // 根据定义，P 的 0 次幂为 1
    for (int i = 1; i <= n; i ++ ) p[i] = p[i - 1] * P;                  // 预处理 p
    for (int i = 1; i <= n; i ++ ) hash_A[i] = hash_A[i - 1] * P + A[i]; // 预处理 hash_A
    for (int i = 1; i <= m; i ++ ) hash_B[i] = hash_B[i - 1] * P + B[i]; // 预处理 hash_B
    for (int i = 1; i <= n; i ++ ) // 二分预处理 cnt
    {
        int l = i, r = i + m, mid; // 二分左边界为 i，右边界为 i + m
        if (r > n + 1) r = n + 1;  // 如果右边界不在 A 中，让其指向 A 的右边界
        while (l < r)              // 二分板子
        {
            mid = l + r >> 1;
            if (get(hash_A, i, mid) != get(hash_B, 1, mid - i + 1)) r = mid;
            else    l = mid + 1;
        }
        cnt[r - i] ++ ; // 二分之后，r 表示的是 B 与 A 匹配的最靠后的位置（从 i 开始），r - i 是 A 从 i 开始的后缀与 B 匹配的最长长度
    }
    while (q -- )       // 处理询问
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", cnt[x]);
    }
    return 0;
}

算法2

($KMP$) $O(N + M + Q)$

这个解法的确比较难想。。需要对 $KMP$ 足够的熟悉。。
先对 $B$ 求 $KMP$，得到 $B$ 的 $next$ 数组。
然后对 $A$ 做一遍匹配，回忆一下匹配的代码：

for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && a[i] != b[j + 1]) j = ne[j];
    if (a[i] == b[j + 1]) j ++ ;
    // blablabla
}

我们发现，在 blablabla 那个位置，$j$ 正好是 $B$ 能匹配 $A$ 的以 $i$ 为终点的最长字符串长度。
也就是说，字符串 $A$ 中，以 $i - j + 1$ 为起点的与 $B$ 匹配的长度最小为 $j$
但是，以 $i$ 为终点的，与 $B$ 匹配的字符串只有 $A[i - j + 1 \sim i]$ 嘛？
不一定，我们发现 $A[i - next[j] + 1 \sim i]$ 也是与 $B$ 的前缀匹配的字符串
同理，$A[i - next[next[j]] + 1 \sim i]$ 也是与 $B$ 的前缀匹配的字符串
$\cdots$
那么，我们在让 cnt[j] ++ 时，就还需要让 cnt[next[j]] ++，还需要让 cnt[next[next[j]]] ++$\cdots$
那我们匹配的时间复杂度就会退化为 $\mathcal O(NM)$ 了，显然是过不了这道题的。
观察下我们操作 cnt[x] 的过程，每次都会让 cnt[next[x]] ++，也就是说，cnt[x] ++了多少次，cnt[next[x]] ++也就要相应的执行多少次。
那么我们就可以先只操作 cnt[j] ++，最后从 $m$ 到 $1$ 循环枚举一遍 cnt[i]，让 cnt[next[i]] += cnt[i] 即可。
注意最后 cnt[i] 存的是满足匹配的前缀至少为 $x$ 的后缀数量，而题目中所要求的满足匹配的前缀恰好为 $x$ 的答案的应为匹配的前缀至少为 x 的后缀数量 减去 匹配的前缀至少为 x + 1 的后缀数量，即 cnt[x] - cnt[x + 1]（后缀和思想），

时间复杂度

求 $B$ 的 $next$ 数组，时间复杂度为 $\mathcal O(M)$
将 $A$ 与 $B$ 做匹配，时间复杂度为 $\mathcal O(N)$
处理询问，时间复杂度为 $\mathcal O(Q)$
故总的时间复杂度为 $\mathcal O(N + M + Q)$

C++ 代码

#include <stdio.h>
#include <string.h>

const int N = 200005;

int n, m, q;
char A[N], B[N];
int ne[N], cnt[N];  // ne 存 B 的 next 数组，cnt 即上述 cnt 数组

int main()
{
    scanf("%d%d%d\n", &n, &m, &q);
    scanf("%s\n%s", A + 1, B + 1);

    for (int i = 2, j = 0; i <= m; i ++ ) // KMP 模板
    {
        while (j && 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 ++ ) // 将 A 与 B 做匹配
    {
        while (j && A[i] != B[j + 1]) j = ne[j];
        if (A[i] == B[j + 1]) j ++ ;
        cnt[j] ++ ;                       // 先只将 cnt[j] ++ 
    }
    for (int i = m; i; i -- ) cnt[ne[i]] += cnt[i]; // 从 m 到 1 枚举 cnt[i]，处理出所有的 cnt[next[i]]

    while (q -- )
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", cnt[x] - cnt[x + 1]); // 输出的结果应为 cnt[x] - cnt[x + 1]
    }
    return 0;
}