没卡 |t1| != |t2| 捏
ywli08
·
·
题解
看到一堆模式串就想到AC自动机。
考虑替换是个什么操作：首先找到匹配串中某一匹配的子串，然后替换掉子串的一个后缀。那么一个替换规则 (s_{i, 1}, s_{i, 2}) 可以拆成这样：
s_{i, 1} = p_1 + S_1 \\
s_{i, 2} = p_2 + S_2 \\
其中 p_1 = p_2, S_1 != S_2 且 LCP(S_1, S_2) = 0
对于所有的 s_{i, 1} 建立AC自动机。对于一个替换规则 (s_{i, 1}, s_{i, 2})，找出 S_2 并