CF985F Isomorphic Strings 题解

这是一篇确定性做法，个人感觉还是很有启发性的。

不妨定义 $s'_i=i-pre_{s_i}$，其中 $pre_{s_i}$ 表示 $s_i$ 上次出现的位置，若为 $s_i$ 第一次出现则 $s'_i=0$。

不难发现，当 $s$ 和 $t$ 同构时，应满足 $s'_i=t'_i$。

考虑怎么求出 $s'$ 与 $t'$，它们的共同特点是原串都是 $S$ 中的一个子串。

观察一下，在 $S$ 中对应 $s$ 这段的 $S'$ 和 $s'$ 有何不同：会有 $O(|\Sigma|)$ 个在 $s$ 中第一次出现的字符，在 $S$ 中并非第一次出现，除此以外的均满足 $S'_i=s'_i$。

它其实相当于将 $S'$ 分成 $O(|\Sigma|)$ 段，每一段要么是，我当前一定是 $0$，要么是，我这一段就是原串。

这时候我们再转化一下题意，把 $S'_{x_i\sim x_i+len-1}=S'_{y_i\sim y_i+len-1}$ 换成 $\texttt{LCP}(a_{x_i},a_{y_i}) \geq len$，其中 $a_i$ 表示 $S'$ 中以 $i$ 结尾的后缀。

不难想到先对 $S'$ 后缀排序，再对 $a'_i$ 进行与 SA 同理的后缀排序，这样子就是转化成了 $\min_{k=rnk2_{x_i}+1}^{rnk2_{y_i}} height2_k$。

现在问题在于如何比较 $a'_i$ 呢？我们是知道 $a_i$ 被分为 $O(|\Sigma|)$ 段的，有若干段是单个数 $0$，其他段是 $S'$ 的一段子串。

求 $a'_i$ 的 $cmp$ 和 $h2$ 其实是同理的，我们暂且以 $cmp$ 为例。

$a'_x$ 和 $a'_y$ 总共还是被分为了 $O(|\Sigma|)$ 段，可以按照长度，直接维护那些段，对于 $0$ 的段我们只需要看另外一位是不是也是 $0$ 就好了。

如果不是 $0$，那么两边的这段都一定在原串出现过，我们直接用原串的 $rnk$ 和 $height$ 数组，查询 $\texttt{LCP}$ 是否 $\geq len$，否则直接比较 $rnk$ 大小即可。

如此往复直到遍历到 $n$ 结束，那么长度小的后缀更小。

用 $st$ 表初始化即可做到比较时 $O(1)$ 查询 $\texttt{LCP}$。总复杂度 $O(n|\Sigma| \log n)$，复杂度瓶颈在对 $a'_i$ 排序。

Submission #331238638 - Codeforces。看上去有点长其实挺简单的。