题目大意 给定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 )，测试数据没有那么毒瘤，足以通过测试。