# 🧠 解题思路（KMP 后缀匹配统计） - 帖子

✨ 第 1 步：求 B 的 KMP 前缀表 ne[]

for (int i = 2, j = 0; i <= m; i++) {
    while (j && b[i] != b[j + 1]) j = ne[j];
    if (b[i] == b[j + 1]) j++;
    ne[i] = j;
}

ne[i] = B[1..i] 的最长相等前后缀长度。

✨ 第 2 步：KMP 匹配统计 f[j]

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++;
    f[j]++;
}

f[j]++ 表示：匹配到 B 的长度为 j 的情况出现一次。

✨ 第 3 步：沿着前缀树向父节点累加

for (int i = m; i; i--) f[ne[i]] += f[i]; 如果完整前缀 i 出现，则其最长前后缀 ne[i] 也会出现。

✨ 第 4 步：回答询问匹配长度恰好等于 x 的个数：

f[x] - f[x+1] 因为 f[x] 是 “至少为 x 的数量”， f[x+1] 是 “至少为 x+1 的数量”。

✅ 完整可复制源码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n, m, q;
char a[N], b[N];
int ne[N];
int f[N];

int main() {
    cin >> n >> m >> q;
    scanf("%s%s", a + 1, b + 1);

    // 求 B 的 KMP 前缀表
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && b[i] != b[j + 1]) j = ne[j];
        if (b[i] == b[j + 1]) j++;
        ne[i] = j;
    }

    // 用 B 匹配 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++;
        f[j]++;
    }

    // 利用前缀树结构把数量往父节点累加
    for (int i = m; i; i--) f[ne[i]] += f[i];

    // 回答询问
    while (q--) {
        int x;
        cin >> x;
        cout << f[x] - f[x + 1] << endl;
    }

    return 0;
}

# 🧠 解题思路（KMP 后缀匹配统计） 审核通过

✨ 第 1 步：求 B 的 KMP 前缀表 ne[]

# 🧠 解题思路（KMP 后缀匹配统计）审核通过