CF700E Cool Slogans

首先可以发现选出的字符串序列一定可以调整成 \(s_i\) 为 \(s_{i + 1}\) 的一段后缀。

注意到这本质上是一个关于子串选择,与子串出现位置有关的问题,于是考虑借助 \(\rm endpos\) 来解决。

那么这个问题本质上就是选择后缀自动机 \(\rm parent\) 树上一条合法的祖先链。

由于 \(\rm endpos\) 集是一个整体,为了优化复杂度我们最好能找到本题当中一个 \(\rm endpos\) 集整体满足的性质:

  • 相同 \(\rm endpos\) 集内的字符串不能同时选入字符串序列。

即 \(\rm endpos\) 集内字符串两两之间不会包含两次。
反证法:若包含两次根据 \(\rm endpos\) 集的性质,这两个字符串可以无限往前延伸,矛盾。

  • 假设 \(v\) 是 \(u\) 在 \(\rm parent\) 树上的祖先,\(\mathrm{longest}(u)\) 为 \(u\) 节点的最长串,则 \(v\) 内所有节点在 \(\mathrm{longest}(u)\) 内出现次数相同。

首先显然 \(v\) 内节点在 \(\mathrm{longest}(u)\) 内出现次数按照长度不增。
反证法:假设对于 \(a, b \in v, b = sa\),有 \(a\) 与 \(b\) 在 \(s\) 内出现次数不同,那么显然只有 \(s\) 会在 \(\mathrm{longest}(u)\) 的外面。
假设将 \(\mathrm{longest}(u)\) 往左延长知道恰好使得 \(b\) 与 \(a\) 出现次数相同的串为 \(t\),根据 \(\rm endpos\) 集的性质 \(\mathrm{endpos}(\mathrm{longest}(u)) \subseteq \mathrm{endpos}(t) \Rightarrow \mathrm{endpos}(\mathrm{longest}(u)) = \mathrm{endpos}(t)\) 可知 \(t \in u\) 而 \(|t| > |\mathrm{longest}(u)|\) 矛盾。

令 \(f_s\) 为以 \(s\) 这个子串作为选出序列的结尾的最大长度,那么可知同一等价类内按照串长 \(f\) 递增(性质三)。

我们只关心最后每个等价类 \(u\) 中 \(f_{\mathrm{longest}(u)}\) 的取值,根据性质一二,转移显然只需要枚举祖先 \(v\) 中所有节点的 \(f_{\mathrm{longest}(v)}\) 查看 \(\mathrm{longest}(v)\) 是否在 \(\mathrm{longest}(u)\) 中出现两次即可,这个可以用线段树合并维护 \(\rm endpos\) 集,直接在线段树上查询 \(\mathrm{longest}(v)\) 在某区间是否出现即可。

这样状态数优化到了线性,但转移复杂度仍然是不能接受的,考虑优化。

注意到每次可以转移的区间一定是一段后缀,根据性质三可以找到第一个可以转移的节点,这里可以使用倍增,复杂度 \(\mathcal{O}(n \log ^ 2n)\).

还可以继续优化,发现我们只关心 \(v\) 往上第一个遇到的极长的 \(f\) 相等的区间内的转移,因为根据性质三 \(f_v\) 至少内取到这个值。

于是只需要记录极长区间的顶部位置即可,这样只需要判定一次,复杂度 \(\mathcal{O}(n \log n)\).

上一篇:《Searching for MobileNetV3》论文笔记


下一篇:【商业源码】生日大放送-Newlife商业源码分享