考虑是怎么查询一组 t 的。对给定二元组分别建立 ACAM。记 s 在 t 上跳时跳到的点的序列为 p_{1, 1..k}, p_{2, 1..k} 然后发现一个替换 i 是可以的，当且仅当存在 j 使得 p_{1,j} 为 i 在被替换串的 ACAM上对应点的子孙，且 p_{2, j} 为 i 在替换串的 ACAM 上的对应点的子孙。
你发现这个东西可能不是很好维护，因为它可能需要知道能不能覆盖完整个需要被替换的区间。我们记 \operatorname{dif}(s, t) 表示从 s 变为 t 最小需要变化的区间。那么刚刚的情况可能会导致需要替换 [2,5] 但是扫到 j=7 的时候有区间 [3, 7] 使得修改了 [3, 5]。于是你可以加一维长度表示需要满足 len \ge k。这样是三维偏序，显然没有办法通过。
考虑怎么优化一下。这个 len \ge p 也太丑了，它直接让我们的做法加了一维。发现这个东西修改的区间长度是固定的。因此对 s_{i, 0/1} 按 \operatorname{dif} 分类，这样就是变为要求 \operatorname{dif}=\operatorname{dif}' 了。然后每次考虑 i \in [1, n] 的二元组就变成矩形加单点和了，可以扔到 dfn 序上扫描线。