专栏文章

字符串基础 III

WWilliam2022
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min76suh
此快照首次捕获于
2025/12/01 21:41
3 个月前
此快照最后确认于
2025/12/01 21:41
3 个月前
查看原文
对于后缀数组 SA 的倍增做法，建议 1010 分钟写完。
因为这是最稳妥的

后缀树

将所有后缀放入字典树，得到后缀树。 把两个后缀，得到的就是它们的 LCP。
heightheight 就是 SA 数组中相邻的两个串在树中 LCA 的深度。
理解可以理解为如果这棵树是自然生长的树，height 就是数论的深度。

height 数组

height[r]=LCP(sa[r],sa[r−1])height[r]=LCP(sa[r],sa[r-1]) （rr 表示 rank）
见贤思齐
  1. 每个后缀看比其大的第一个，即为见贤。
  2. 然后再直接匹配就是 思齐。

求解 height

朴素暴力

直接暴力匹配 判断最长公共前缀长度是 O(n)O(n)。
O(n2)O(n^2)，但是在随机数据跑的飞快。

二分+哈希

判断最长公共前缀长度是 O(log⁡n)O(\log n)。
O(nlog⁡n)O(n\log n)

线性

根据引理 height[i−1]−1≤height[i]height[i-1]-1 \leq height[i]。
O(n)O(n)
故事
ii 向 i−1i-1 抄作业，一定能抄到 height[i−1]−1height[i-1]-1

应用

后缀 LCP

LCP(sa[x],sa[y])=min⁡r∈(x,y]height[r]LCP(sa[x],sa[y]) = \min_{r \in (x,y]}{height[r]} 使用简化问题证明，使用 RMQ 算法实现。

子串 LCP

对两个后缀求 LCP，然后截断。

不同子串数量

考虑简化问题：
abcde 全不同
aaaaa 全同
结合以下就是 abcda：
发现对于 abcde 中的 heightheight 多出一个 11。
然后推广就能得到。
ans=n(n+1)2−∑height[i]ans=\frac{n(n+1)}{2} - \sum height[i]

最长重复字串

排序以后物以类聚
思考
最长：二分
哈希：物以类聚 字串：后缀的前缀

二分+哈希

二分 CC
提取所有长度为 CC 的字串，然后哈希判重。

height

max⁡height[i]\max{height[i]}

最长不重叠字串

二分+哈希

经仍然可解。

height

二分答案

例1

题意

给定一个序列。 最长重复 kk 次的字串最长长度。
显然哈希可解，但是学 height。

思考

  1. 排序以后物以类聚
  2. 简化问题（k=2k=2，k=3k=3）

结果

对每个长度为 k−1k-1 的滑动窗口求 min⁡\min，最后的结果求 max⁡\max

例2

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...