题意: 给一个串,\(Q\) 次询问区间 \([l,r]\) 中至少出现两次的子串的最大长度 。
写LCT是什么东东
以下做法很经典:
先求出 SA 以及 height
数组,然后按 height
从大到小每次加入一条连接 \(sa_i\) 与 \(sa_{i+1}\) 的边,并用并查集维护每个连通块 。这样由经典结论 \(\mathrm{lcp}(i,j)=\min_{rank_i\le rank_k\le rank_j-1}\{height_k\}\) 可知,若已加的边中 height
最小值为 \(k\),那么 \(\mathrm{lcp}(i,j)\ge k\) 当且仅当 \(i,j\) 当前在同一连通块内 。
在本题中,每次使用启发式合并+可持久化线段树维护每个 \(i\) 在连通块中的后继(即下一个比它大的),查询时二分答案 \(L\),看长度为 \(L\) 时是否有 \(\min_{i\le k\le j}suf_k\le r-L+1\) 即可 。
时间复杂度 \(O(n\log^2n)\) 。这玩意不好过LCT
【字符串 P7361 「JZOI-1」拜神】
推荐阅读
- 「Tubian」Tubian0.4!完全开源!
- 「Tubian」Tubian0.41!支持Windows QQ微信!
- 「产品运营」研发效能之DevOps平台如何运营?
- Python-函数-字符串函数
- .NET源码学习 [算法2-数组与字符串的查找与匹配]
- 如何理解「数字化是 IT 公司在给传统企业贩卖焦虑」?
- 俄乌战局迎重大变化?来看新进展「俄乌最新战况」
- 牡丹江一小区11只宠物犬相继被毒死「牡丹江落水狗」
- 教育局回应河南一老师晒节日礼物「河南教师节活动」
- 七朵农副「认领一瓣蒜」安全吗?