CF985F Isomorphic Strings 题解

Loser_Syx · 2025-07-29 16:56:27 · 题解

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

不妨定义 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 为例。