字符串

Cxny

字符串只会哈希。

后缀数组 SA

暑假就开始看……直到现在才搞明白。

定义 表示排名为 的后缀的位置, 表示以 开头的后缀的排名。有 。

考虑如何求出 数组。

尝试倍增,对于每个长度为 的子串求出它在长度相等子串中的排名。

对于长度为 的子串直接解决。接下来考虑合并。

假设需要求出长度为 的子串之间的排名。将 为第一关键字, (不存在则视为无穷小)为第二关键字排序,就得到了它们的排名。

如此倍增,直到 。此时 即为所求。

采用基数排序,复杂度 。据说还有高妙的 解法,但没必要。


height 数组

接下来定义 表示从 开始的后缀的最长公共前缀。

定义 表示排名为 的后缀与排名 的后缀的最长公共前缀,即 。

引理

可以利用引理暴力求出 。复杂度 。

证明、应用等参考 OI Wiki。


[NOI2015] 品酒大会

先不考虑第二问。

根据题意,我们只需要求出 的对数,再做一遍后缀和即可。

注意到

考虑将 从打到小插入。每次操作形如合并两段区间,两段区间内最小值均大于当前插入的值。

因此,设左右两段大小分别为 ,则这个点的贡献即为 。

至于第二问,维护每段的最大值与最小值即可。

  • Post title:字符串
  • Post author:Cxny
  • Create time:2022-12-05 20:54:19
  • Post link:https://cxny.github.io/2022/12/05/string/
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.