2025 谐音替换 · 方案二叠串+AC自动机

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 2799 字
规则对编码成叠串，答案即叠串在询问编码串中的出现次数
2025
AC自动机
正文

// CSP-S 2025 复赛 T3 · 谐音替换（方案二：叠串编码 + AC 自动机，满分）
// 原题：https://oj.yecheng.tv/p/2468
// 题意：同方案一（|t| 总长 ≤ 5e6，需满分口径）。
// 思路（把「能否替换」变成「是否为子串」）：
//   对每对 (a, b)（a != b），取首末失配位 l、r，编码成叠串
//   P = a[0..l) + '{' + a[l..r] + '{' + b[l..r] + '{' + a(r..]
//   其中 '{' 不在小写字母内，用来挡住跨区间的错误匹配。
//   询问串 (t1, t2) 用同一规则编码后：这对规则可行
//   <=> P 是询问编码串的子串。
//   把全部 P 插入 AC 自动机（26 字母 + '{' 共 27 叉），询问时沿
//   goto 图走一遍，沿途累加 fail 树上前缀计数即答案。
// 复杂度：预处理 O(总长)，每次询问 O(|t|)。内存约 600MB，需 2GB。
// 易错点：
//   1. a == b 的规则对必须跳过，否则 f() 求失配位死循环；
//   2. 询问两串长度不等直接输出 0，不能进编码；
//   3. trie 静态数组 5.7e6 × 27 个 int，开小必 MLE；
//   4. '{' 的编码位是 26（'{' - 'a' = -58 溢出，须单独映射）。
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

const int MAXN = 5700005;
int trie[MAXN][27];
int fail_[MAXN];
int cnt_[MAXN];
int tot = 1;

// '{' 与小写字母统一映射：'{' -> 26
inline int id(char c) { return c == '{' ? 26 : c - 'a'; }

void insert(const string &s) {
    int p = 1;
    for (char c : s) {
        int x = id(c);
        if (trie[p][x] == 0) trie[p][x] = ++tot;
        p = trie[p][x];
    }
    cnt_[p]++;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 27; i++) {
        int v = trie[1][i];
        if (v) { fail_[v] = 1; q.push(v); }
        else trie[1][i] = 1;
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt_[u] += cnt_[fail_[u]];
        for (int i = 0; i < 27; i++) {
            int v = trie[u][i];
            if (v) { fail_[v] = trie[fail_[u]][i]; q.push(v); }
            else trie[u][i] = trie[fail_[u]][i];
        }
    }
}

ll check(const string &s) {
    ll res = 0;
    int p = 1;
    for (char c : s) {
        p = trie[p][id(c)];
        res += cnt_[p];
    }
    return res;
}

// a = x + y + z, b = x + y' + z -> x + '{' + y + '{' + y' + '{' + z
string f(const string &a, const string &b) {
    int siz = (int)a.size();
    int l = 0, r = siz - 1;
    while (a[l] == b[l]) l++;
    while (a[r] == b[r]) r--;
    string res;
    res.append(a, 0, l);
    res.push_back('{');
    res.append(a, l, r - l + 1);
    res.push_back('{');
    res.append(b, l, r - l + 1);
    res.push_back('{');
    res.append(a, r + 1, siz - r - 1);
    return res;
}

static char buf[5000005 + 10];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%s", buf); string a = buf;
        scanf("%s", buf); string b = buf;
        if (a == b) continue; // a=b 的对无法贡献答案，且失配位不存在
        insert(f(a, b));
    }
    build();
    for (int j = 0; j < q; j++) {
        scanf("%s", buf); string t1 = buf;
        scanf("%s", buf); string t2 = buf;
        if (t1.size() != t2.size()) { printf("0\n"); continue; }
        printf("%lld\n", check(f(t1, t2)));
    }
    return 0;
}
2025 谐音替换 · 方案二 叠串+AC自动机

正文

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

2025 谐音替换 · 方案二叠串+AC自动机
