P14363 [CSP-S 2025] 谐音替换
题目大意
给定 n 个长度相等的字符串二元组 (si,1,si,2)。
一次替换操作:在字符串 t 中选一个与某个 si,1 相等的子串,将其替换为对应的 si,2(只替换一处)。
对于 q 个询问,每个询问给出两个不同字符串 tj,1,tj,2,求有多少种不同的替换方式能将 tj,1 变为 tj,2。
两种替换不同当且仅当选择的子串位置不同或使用的二元组编号不同。
数据范围:1≤n,q≤2×105,2≤L1,L2≤5×106,其中 L1=∑i=1n(∣si,1∣+∣si,2∣),L2=∑j=1q(∣tj,1∣+∣tj,2∣)。
所有字符串仅含小写英文字母,且每个二元组内两个字符串长度相等,查询的两个字符串互不相同。
特殊性质 A:q=1;特殊性质 B:所有字符串均为“特殊”字符串(只含字符 a 和 b,且 b 恰好出现一次)。
题解
分享一个十分天才的想法(来自 Register_int):容易发现,如果我们设两个字符串 s1=A+B+C,s2=A+D+C,此时的 A,C 表示这两个字符串的最长公共前/后缀,此时 A?BD?C 就可以表示这个替换(这里的 ? 是特殊字符,直接加在字符串中),由于我们只能替换一次,对模式串和匹配串都这么做以后 B,D 一定是需要更换的地方,也就是说我们可以用多模式串匹配代替普通的替换,如果匹配成功,那么一定可以进行替换(因为此处 ? 限制了 A,B,C,D 的位置)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, S = 5e6 + 10, C = 27;
int n, m;
int tr[S + 2 * N + 10][C], cnt[S + 2 * N + 10], idx;
char s[S], s1[S], s2[S];
int q[S + 2 * N + 10], ne[S + 2 * N + 10];
int sum[S + 2 * N + 10];
int get(char c) {
if (c == '?') return 26;
return c - 'a';
}
void input(int &len1, int &len2) {
char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
len1 = 0;
while ('a' <= c && c <= 'z') {
s1[len1++] = c;
c = getchar();
}
while (c < 'a' || c > 'z') c = getchar();
len2 = 0;
while ('a' <= c && c <= 'z') {
s2[len2++] = c;
c = getchar();
}
}
int calc() {
int len1 = 0, len2 = 0;
input(len1, len2);
int j = 0, k = len1 - 1, cnt = 0;
while (j < len1 && s1[j] == s2[j])
s[cnt++] = s1[j++];
s[cnt++] = '?';
while (k >= j && s1[k] == s2[k])
k--;
for (int l = j; l <= k; l++)
s[cnt++] = s1[l];
for (int l = j; l <= k; l++)
s[cnt++] = s2[l];
s[cnt++] = '?';
for (int l = k + 1; l < len1; l++)
s[cnt++] = s1[l];
s[cnt] = '\0';
return cnt;
}
void insert() {
int p = 0;
for (int i = 0; s[i]; i++) {
int t = get(s[i]);
if (!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
}
cnt[p]++;
}
void build() {
int hh = 0, tt = -1;
for (int i = 0; i < C; i++)
if (tr[0][i]) q[++tt] = tr[0][i];
while (hh <= tt) {
int t = q[hh++];
for (int i = 0; i < C; i++) {
int p = tr[t][i];
if (!p) {
tr[t][i] = tr[ne[t]][i];
} else {
ne[p] = tr[ne[t]][i];
q[++tt] = p;
}
}
}
sum[0] = cnt[0];
for (int i = 0; i <= tt; i++) {
int p = q[i];
sum[p] = cnt[p] + sum[ne[p]];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int len = calc();
insert();
for (int l = 0; l < len; l++) s[l] = 0;
}
build();
while (m--) {
int len = calc();
long long res = 0;
int j = 0;
for (int i = 0; i < len; i++) {
int t = get(s[i]);
j = tr[j][t];
res += sum[j];
}
printf("%lld\n", res);
for (int l = 0; l < len; l++) s[l] = 0;
}
return 0;
}(此代码使用 DeepSeek 进行格式化)。
