形式化题目

给定长度 $N$ 的串 $A$、长度 $M$ 的串 $B$。对每个起点 $i \in [1, N]$，定义它的匹配长度

即后缀 $A[i..N]$ 与 $B$ 的最长公共前缀长度（受 $B$ 的长度限制，最多匹配 $M$ 个字符）。 题目给出 $Q$ 个询问，每个询问一个整数 $x$，要求输出满足 $L_i = x$ 的起点个数

$x$ 可以超过 $N$ 或 $M$，此时答案为 $0$。

题面示例：A = $ `aabcde`，B = $ ab，六个后缀 aabcde、abcde、bcde、cde、de、e 的匹配长度依次是 $1, 2, 0, 0, 0, 0$。下表把「后缀、与 $B$ 的公共前缀、匹配长度」逐行对齐， 注意长度是截断在 $B$ 的末尾的：

于是 $\mathrm{cnt}[0] = 4$、$\mathrm{cnt}[1] = 1$、$\mathrm{cnt}[2] = 1$，$x \geqslant 3$ 全为 $0$， 与样例输出 4 1 1 0 0 一致。

正解

思路

朴素做法的瓶颈。 最直接的办法是对每个起点 $i$ 从零开始逐字符比：令 $k$ 从 $0$ 递增， 只要 $k < M$、$i + k \leqslant N$ 且 $A[i+k] = B[k+1]$ 就让 $k$ 加一。每趟最多比 $M$ 个字符， 总代价 $O(NM)$；当 $A$ 与 $B$ 都是 aaaa... 时 $N = M = 2 \times 10^5$，要比较 $4 \times 10^{10}$ 次，必须优化。

瓶颈在于信息没有共享：$A$ 的相邻后缀之间高度重合，前一个位置比过的字符，后一个位置 又从头比了一遍。而且要注意，这题问的并不是「$B$ 在 $A$ 的哪些位置完整出现」这一个布尔 信息，而是每个后缀与 $B$ 的 LCP 长度这一整族量——只报告匹配位置的算法（str.find、 单次 KMP 匹配）拿不到它。

把整族 LCP 交给 Z 函数。 Z 函数的定义恰好就是 LCP：

把两个串拼起来，让 $B$ 当「模式串」、$A$ 当「被对齐的文本」：

对 $A$ 的起点 $i$，它在 $s$ 中的下标是 $j = M + 1 + i$，此时 $s[j..]$ 与 $s[1..]$ 的最长 公共前缀就是 $B$ 与 $A[i..]$ 的最长公共前缀，也就是 $L_i$。一次 Z 函数就同时算出了所有 起点的答案。

分隔符 $\#$ 有两个作用，缺一不可：

1. 它大于所有小写字母、不等于 $A$ 或 $B$ 的任何字符，所以匹配不可能「跨过」它把 $B$ 的 末尾和 $A$ 的开头接起来；
2. 更关键的是，它让 $z[j] \leqslant M$：一旦比到 $s[M] = \#$ 就必然失配， LCP 天然被截断在 $B$ 的末尾，正好符合题目「最多匹配 $M$ 个字符」的定义，不需要再写 额外的 min 或截断判断。

延续上面的样例，s = $ `ab{aabcde`（`{` 就是 $\#）的 $z$ 数组是 0 0 0 1 2 0 0 0 0，切掉 $B$ 段和分隔符后的 1 2 0 0 0 0 正是 $L_1 \dots L_6$：

观察重点：下标 $4$、$5$ 对应 $A$ 的前两个起点，其 $z$ 值恰好是匹配长度 $1$、$2$；下标 6 往后是 bcde 与 B = $ `ab` 首字符就不同，全是 $0。也可以看下标 $4$：$s[4..]$ 与 ab{aabcde 的首字符都是 a，但第二位 a $\neq$ b 于是停住，$z = 1$——匹配在 $B$ 的中途结束。

Z 算法为什么线性。 维护当前右端最靠后的一个匹配段（称为 Z 盒）$[l, r)$，其中 $s[l..r-1] = s[1..r-l]$。对位置 $j$：

• 若 $j < r$，由 Z 盒的对称性，$z[j]$ 至少是 $\min(r - j,\ z[j - l])$——可以直接借用左侧 对称位置已经算好的值，再从这个下界继续往右比；
• 每轮结束时，若 $j + z[j] > r$ 就把盒子右移到 $j + z[j]$。

盒子右端 $r$ 单调不减且不超过 $|s|$，因此「盒内成功比较」的总次数被 $r$ 的总增量限制， 而每次失败比较都恰好发生在盒子右端、同样被 $r$ 的总增量限制；整趟均摊 $O(|s|)$。

从长度到答案：直方图。 拿到 $L_1, \dots, L_N$ 之后，询问只是「某个值出现了几次」。 开一个长度 $M + 1$ 的桶 hit，对每个 $L_i$ 做一次 hit[L_i] += 1，则询问 $x$ 的答案就是 hit[x]（$x > M$ 时直接为 $0$，因为 $L_i \leqslant M$ 恒成立）。这样每个询问 $O(1)$， 不必对每个询问重新扫描一遍 $L$。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 12:29
# update_at: 2026-10-01 12:29

import sys

DELIM = ord('z') + 1  # 分隔符：大于所有小写字母，保证匹配不会越过 B 的结尾（长度恒不超过 M）


def z_function(seq: bytes) -> list[int]:
    """Z 函数：z[i] 是 seq 与 seq[i:] 的最长公共前缀长度，均摊 O(|seq|)。"""
    z = [0] * len(seq)
    left = right = 0  # 目前右端最靠后的匹配段 [left, right)
    for i in range(1, len(seq)):
        if i < right:
            z[i] = min(right - i, z[i - left])  # 借用左端对称位置的答案，再截断到已知段的右端
        while i + z[i] < len(seq) and seq[z[i]] == seq[i + z[i]]:
            z[i] += 1
        if i + z[i] > right:
            left, right = i, i + z[i]
    return z


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))
    q = int(next(data))
    a = next(data)
    b = next(data)
    queries = [int(next(data)) for _ in range(q)]

    # 拼成 B + 分隔符 + A，一次 Z 函数就同时给出 A 每个后缀与 B 的匹配长度
    z = z_function(b + bytes((DELIM,)) + a)[m + 1:]

    hit = [0] * (m + 1)  # hit[length] = 匹配长度恰好为 length 的后缀个数
    for length in z:
        hit[length] += 1

    ans = [hit[t] if t <= m else 0 for t in queries]  # 匹配长度不会超过 M
    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:52
 * update_at: 2026-10-06 16:52
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;              // A 串长度上限
const int MAXM = 200005;              // B 串长度上限
const int MAXS = MAXN + MAXM + 5;     // 拼接串长度上限：B + 分隔符 + A

typedef long long ll;

ll n, m, q;
char A[MAXN];       // 被匹配的文本串
char B[MAXM];       // 模式串
char s[MAXS];       // 拼接串 s = B + 分隔符 + A，下标从 1 开始
int z[MAXS];        // z[i] 表示 s 与 s[i..] 的最长公共前缀长度
int hit[MAXM];      // hit[len] 表示匹配长度恰好为 len 的后缀个数

// 计算 s[1..len] 的 Z 数组，均摊 O(len)。
void z_function(int len) {
    z[1] = 0;
    int left = 1, right = 1; // 当前右端最靠后的匹配段 [left, right)
    for (int i = 2; i <= len; i++) {
        if (i < right) {
            // 借用左侧对称位置的答案，并截断到已知段的右端
            z[i] = min(right - i, z[i - left + 1]);
        }
        // 从下界继续往右逐字符比较
        while (i + z[i] <= len && s[z[i] + 1] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > right) {
            left = i;
            right = i + z[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    cin >> (A + 1);
    cin >> (B + 1);

    // 拼接：s[1..m] 放 B，s[m+1] 放分隔符，s[m+2..m+1+n] 放 A
    for (int i = 1; i <= m; i++) {
        s[i] = B[i];
    }
    s[m + 1] = 'z' + 1; // 大于所有小写字母，保证匹配不会跨过分隔符
    for (int i = 1; i <= n; i++) {
        s[m + 1 + i] = A[i];
    }
    z_function(m + 1 + n);

    // A 的起点 i 在 s 中的下标是 m+1+i，其 z 值就是它与 B 的最长公共前缀
    for (int i = 1; i <= n; i++) {
        hit[z[m + 1 + i]]++;
    }

    // 每个询问 O(1) 回答；匹配长度不会超过 M
    for (int i = 1; i <= q; i++) {
        ll x;
        cin >> x;
        if (x >= 0 && x <= m) {
            cout << hit[x] << '\n';
        } else {
            cout << 0 << '\n';
        }
    }

    return 0;
}

z_function(seq) 是 Z 算法本体，返回整个 $z$ 数组；solve 里 z_function(b + bytes((DELIM,)) + a)[m + 1:] 一次完成拼接与切片，切片后下标 $j$ 就对应 起点 $j$；随后的 hit 循环建直方图，最后一行按询问顺序 $O(1)$ 取值输出，t <= m 同时挡住「越界」和「不可能存在的匹配长度」两种情况。

复杂度

• 时间 $O(N + M + Q)$：拼接串长 $M + 1 + N$，Z 函数均摊线性；建直方图 $O(N)$；$Q$ 个询问 各 $O(1)$。
• 空间 $O(N + M)$：拼接串与 $z$ 数组各占 $O(N + M)$，直方图占 $O(M)$。

总结

• 题目本质是「求 $A$ 每个后缀与 $B$ 的 LCP 的分布」，而不是「$B$ 在 $A$ 中出现在哪里」； 后者（str.find、单次 KMP 匹配）拿不到这族长度。
• 把 $B$ 放在前面、用不出现在字母表中的分隔符隔开 $A$，$A$ 段的 Z 数组就直接给出全部 $L_i$；分隔符同时把 LCP 天然截断到 $M$，与题目定义自动吻合。
• 长度到手后只需一个大小为 $M+1$ 的直方图，$Q$ 个询问各自 $O(1)$，总复杂度 $O(N + M + Q)$、空间 $O(N + M)$。