题解：P14363 [CSP-S 2025] 谐音替换 / replace

· · 题解

我的考场思路。

刚开始大概看题的时候发现 T2 T3 一个图一个字符串两眼一黑，因为我都不擅长。但是仔细一看也不是特别难。

首先抛开两个字符串相等或不同长的情况。

定义一个字符串替换 (s_1,s_2) 的“本质”，指的是 s_1,s_2 第一个和最后一个不一样的字符的位置，中间的这一段子串 (s'_1,s'_2)。中间的这一段把字符串分成了三个部分，一个前缀，一个“本质”，一个后缀。(s_1,s_2) 的前后缀是相同的。

同理定义询问 (t_1,t_2) 的“本质”。不难发现一个字符串替换 (s_1,s_2) 在这个询问产生贡献，必要条件是它们的“本质”相同。而两个字符串替换 (s_{i,1},s_{i,2}),(s_{j,1},s_{j,2}) 要能对同一个询问产生贡献，也需要它们的“本质”相同。

那么把“本质”相同的字符串对“归入一类”。去掉中间这部分后，t_1,t_2 的前后缀相等。为了方便，称一个字符串 s 去掉中间那一段后的前后缀分别为 s_l,s_r，称（去掉“本质”部分后相同的）字符串替换或询问 (s_1,s_2) 为 (s)。这样处理询问，就相当于在那些同类的 (s)_l 中匹配 (t)_l 作为后缀，在同类的 (s)_r 中匹配 (t)_r 作为前缀，然后输出两端能同时匹配的 (s) 的个数。这里前后用两个 trie 加上一个一边可以到达的 (s) 编号的标记就可以解决问题，至少我是这样做的（前缀部分需要 reverse 一下）。

update：经过提醒，我发现我的考场方法在此处满足要求的结点数量很多的时候可能炸掉。这里的正解应该是转 dfn，然后离线，用树状数组维护。

可以用字符串哈希处理这些“本质”，来进行“分类”。然后就做完了……吗？

别忘了刚开始抛弃了 s_1,s_2 相同的情况，以及 t_1,t_2 长度不等的情况。幸运的是，样例里面是有这两种情况的。遇到前者，直接把这对修改忽略即可，因为题目保证了 t_1,t_2 不等，这对修改是不可能产生贡献的。遇到后者，输出 0 即可。

考场时脑抽忘记字符串比较很花时间写了个 map<pair<string,string>,int>，可能会挂分。

因为要 AFO 了，所以代码拿到后有时间再补。如果那时审核队列比较长的话可能会先放到这里。里面也可能有一些补充的内容。