怎么一堆大佬写了题解，算了看见队爷假装没看见。 温馨提示：题目要求只能替换一次。注意到每个 (si,1,si,2)(s_{i,1},s_{i,2})(si,1 ,si,2 ) 实际上的替换是把除了它两端的相同字符以外的中间那一部分，因为两端的字符替换了等于没替换。而每个 (ti,1,ti,2)(t_{i,1},t_{i,2})(ti,1 ,ti,2 ) 其实是需要一个 sss 二元组使自己两端极长相同子段外的中间部分恰好被替换掉，因此要求 sss 和 ttt 二者中间的核心部分相同。同时也需要符合替换条件，也就是 sss 替换的部分放进 ttt 串里两端多余的部分是恰好匹配的。 这启发我们像 P9196 一样重构串。首先中间核心部分是匹配关键，由于 si,1=si,2s_{i,1}=s_{i,2}si,1 =si,2 其长度恰好是 sss 串单个的两倍，具有单一性，直接两端加上特殊字符，剩下部分贴在特殊字符两旁用于匹配，即拆分 (si,1,si,2)(s_{i,1},s_{i,2})(si,1 ,si,2 ) 和 (ti,1,ti,2)(t_{i,1},t_{i,2})(ti,1 ,ti,2 ) 二元组为字符串 A?BD?C\text{A?BD?C}A?BD?C，其中 ?\text{?}? 为特殊字符，两串分别为 ABC\text{ABC}ABC 和 ADC\text{ADC}ADC，A\text{A}A 和 C\text{C}C 分别为两个串的最长公共前后缀。 用 ACAM 跑多模匹配即可，由于每个 sss 最多在每个 ttt 中出现一次，出现至少一次的 sss 串数量等于所有 sss 串的出现次数，可以通过对 fail 进行前缀和规避暴力跳，这样我们在所匹配的这个节点即可直接计算贡献。 时间复杂度 O(∣∑∣L1+L2)O(|\sum|L_1+L_2)O(∣∑∣L1 +L2 )

Difficulty：5.3 / Easy+ Tag：Trie，树状数组 省选试机时挑的题，总共写了 1h（试机时）+30min（刚刚写的）。 这个转化不用说了吧还是说一下吧。就是可以转化成两个串相同前后缀加上中间那一坨，然后查询一个转化后的模式串可以包多少个转化后的文本串。 这个显然可以哈希记录中间那一坨，然后对每一个中间那一坨，分别给前后缀建一个 Trie。 你说得对，但是哈希还是太吃操作和码量了。 办法还是有的。就是把中间那一坨拼接在前后缀前面，当成判断的一部分。这样就只需要建两个 Trie 了。 我实现的时候因为前缀需要倒序遍历，所以其实是拼在后面再反转的，也相当于拼在前面了。 然后我们对两棵 Trie dfs，然后查询文本串所在的 dfn 区间，就转化成一个矩形加单点查问题了。这不神奇吗。 这个显然可以扫扫扫。 字典树空间一开始以为要开 2L+2n2L+2n2L+2n，但后来发现 L=∑T1+T2=2∑T1L=\sum T_1+T_2=2\sum T_1L=∑T1 +T2 =2∑T1 ，所以开 L+2nL+2nL+2n 就足够了。 时间复杂度：O(∣Σ∣L+(n+q)log⁡L)O(|\Sigma|L+(n+q)\log L)O(∣Σ∣L+(n+q)logL)。

题目大意 给定nnn个形如s ts\space ts t的变换规则，再询问qqq次，每次询问给出两个字符串sss和ttt，计算有多少种单次替换能将sss变为ttt。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目分析 要从sss中找替换规则中的子串，显然是一个多模式匹配问题，可以使用AC自动机解决。 接下来就该思考如何将两个字符串转换为一个字符串，因为AC自动机适用于单个串匹配，如果不进行转换，每次都要以O(∣t∣)O(|t|)O(∣t∣)的时间复杂度比较。以下思路参考了洛谷用户@Register_int： 把变换s→ts\rightarrow ts→t记为A?CD?BA?CD?BA?CD?B，其中A,B,C,DA,B,C,DA,B,C,D都为字符串，AAA和BBB分别表示sss和ttt的最长公共前缀和后缀，CCC和DDD分别表示sss和ttt其它的部分，对询问也进行同样的变换。 正确性说明：若变换s→ts\rightarrow ts→t是一个合法的变换，设它表示为E?GH?FE?GH?FE?GH?F，EEE实际上不会影响开头和结尾未触及的部分，即未被修改的部分必然完全相同，且这部分就位于字符串的两端。而中间需要进行变换的部分，GGG一定对应CCC，HHH一定对应DDD，即改变了需要改变的位置。这样不需要改变的部分没有改变，需要改变的部分改变了，即这个变换可行。 变换中的???可以变为'{'，因为它位于′z′'z'′z′之后。 变换代码如下： 求failfailfail指针和AC自动机操作代码如下： 这样做时间复杂度最坏情况下能达到O((∑i=1nsi,1+si,2)2)O((\sum_{i=1}^{n} s_{i,1}+s_{i,2})^2)O((∑i=1n si,1 +si,2 )2)量级，能得到909090分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 优化 接下来考虑优化。 AC自动机常用的优化方法是拓扑排序优化，但拓扑排序优化需要遍历整个字典树，甚至可能提高时间复杂度，因此拓扑排序优化不可行。 我们注意到，在查询过程中，实际上访问了大量重复字符，一些endendend标记为000的节点也被访问了。为了避免这种情况，可以使用后缀链跳跃的方法，为每个节点定义nextnextnext为当前后缀链上下一个有endendend标记的节点，这样操作时每个模式串只访问一次，与ttt的长度无关。 如何求得nextnextnext？分两种情况，若failfailfail指针指向的节点带有endendend标记，直接指向它，否则继承它的nextnextnext，代码如下： 这时候queryqueryquery函数的i=t[i].faili=t[i].faili=t[i].fail就可以改为i=t[i].nxti=t[i].nxti=t[i].nxt ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完整代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 复杂度分析 空间复杂度显然为O(L1)O(L_1)O(L1 )。 对每个函数分析时间复杂度： BUILDBUILDBUILD函数：共要插入L1L_1L1 个字符，因此时间复杂度为O(L1)O(L_1)O(L1 )； GETFAILGETFAILGETFAIL函数：需要遍历每个节点及其子节点，因此时间复杂度为O(26L1)=O(L1)O(26L_1)=O(L_1)O(26L1 )=O(L1 )； QUERYQUERYQUERY函数：首先遍历每个询问字符，时间复杂度为O(L2)O(L_2)O(L2 )。每次询问，由于路径压缩优化，每个变换规则至多遍历一次，最坏情况下遍历NNN次。共有QQQ次询问，因此时间复杂度<O(NQ+L2)<O(NQ+L_2)<O(NQ+L2 )； FFF函数：显然为O(L1)O(L_1)O(L1 )。 因此总时间复杂度上限为O(nq+L2)O(nq+L_2)O(nq+L2 )，测试数据没有那么毒瘤，足以通过测试。

解析 我们注意到不管是数据还是询问，只要能对上，那肯定是前缀相同后缀相同，中间有一段不同的修改，我们预处理出每一对中间的实际转换的内容，容易发现，实际产生贡献的询问和转换串，中间的修改肯定是完全相同的，而转换串两边的前后缀分别是询问串前缀的后缀和后缀的前缀，也就是被包含在询问串的中间。那么，我们对中间的转换哈希一下，然后对于任何中间相同的串，我们对前缀和后缀分别建好 trie，这样对每个询问，就相当于查询两边的 trie 上都是当前点的祖先的点有几个。对于这个问题，我们可以对 trie 计算 dfs 序之后将其转换为二维数点问题，使用树状数组即可维护，最终的总复杂度为 (O(∣S∣+∣T∣+(q+n)log⁡(q+n)))(O(|S|+|T|+(q+n)\log(q+n)))(O(∣S∣+∣T∣+(q+n)log(q+n))) 。 答案