2025 谐音替换 · 方案一逐对逐位置暴力

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 2174 字

窗口须盖住全部失配位，逐规则逐起点比对计数

2025
AC自动机

正文

// CSP-S 2025 复赛 T3 · 谐音替换（方案一：逐对逐位置暴力判定）
// 原题：https://oj.yecheng.tv/p/2468
// 题意：n 条替换规则 (s1, s2)，|s1| = |s2|。替换：若 t1 的某个
// 子串 y 恰好等于某条规则的 s1，则可把这一段整体换成对应的 s2。
// 每次询问给 (t1, t2)（t1 != t2），问有多少种替换能得到 t2；
// 「子串位置不同」或「规则不同」都算不同种。
// （本题在 OJ 上为标准输入输出，无需文件重定向。）
// 思路：
//   替换不改变长度，|t1| != |t2| 直接答 0。替换后的串只在窗口
//   [l, l+L) 内与 t1 不同（L = |s1|），故窗口必须盖住 t1 与 t2
//   的全部失配位。预处理失配位的前缀/后缀计数，然后对每条规则
//   枚举合法起点：窗口内 t1 逐位等于 s1、t2 逐位等于 s2，
//   窗口外两侧失配计数为 0，满足则方案加一。
// 复杂度：O(q · n · |t| · |s|)，小数据可过；满分见方案二。
// 易错点：
//   1. s1 == s2 的规则不用特判——t1 != t2 时自然贡献 0；
//   2. 窗口必须同时盖住首、末两个失配位，起点范围据此收缩；
//   3. 同一条规则在多个位置出现要分别计数。
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<string> va(n), vb(n);
    static char buf[5000005];
    for (int i = 0; i < n; i++) {
        scanf("%s", buf); va[i] = buf;
        scanf("%s", buf); vb[i] = buf;
    }
    while (q--) {
        scanf("%s", buf); string t1 = buf;
        scanf("%s", buf); string t2 = buf;
        int len = (int)t1.size();
        if ((int)t2.size() != len) { printf("0\n"); continue; }
        // 失配位前后缀计数
        vector<int> pre(len + 1, 0), suf(len + 1, 0);
        for (int p = 0; p < len; p++) pre[p + 1] = pre[p] + (t1[p] != t2[p]);
        for (int p = len - 1; p >= 0; p--) suf[p] = suf[p + 1] + (t1[p] != t2[p]);
        int l0 = -1, r0 = -1;
        for (int p = 0; p < len; p++)
            if (t1[p] != t2[p]) { l0 = p; break; }
        for (int p = len - 1; p >= 0; p--)
            if (t1[p] != t2[p]) { r0 = p; break; }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            int L = (int)va[i].size();
            if (L > len) continue;
            int lo = r0 - L + 1 > 0 ? r0 - L + 1 : 0;
            int hi = l0 < len - L ? l0 : len - L;
            for (int l = lo; l <= hi; l++) {
                bool ok = pre[l] == 0 && suf[l + L] == 0;
                for (int p = 0; p < L && ok; p++)
                    ok = t1[l + p] == va[i][p] && t2[l + p] == vb[i][p];
                if (ok) ans++;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

2025 谐音替换 · 方案一 逐对逐位置暴力

正文

CSP-S 标程 · 复赛真题的其它内容

2025 谐音替换 · 方案一逐对逐位置暴力