弱周期定理WPL (Weak Periodicity Lemma.)
弱周期定理WPL (Weak Periodicity Lemma.)
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121712
因为 可以去到 ，因此可以表示成 的形式。
本质：划分等价类，等价类有一个迭代的过程，怎么都可以走到 ，但走不到更小的
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-25
后缀数组SA
后缀数组SA 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134042245 https://uoj.ac/problem/35 通过倍增实现排序 类似基数排序，先排后面，再排前面 排的过程可以拿桶排优化 设 h(i)=lcp(sa[rk[i]−1],i)h(i)=lcp(sa[rk[i]-1],i)h(i)=lcp(sa[rk[i]−1],i) 有 h(i)≥h(i−1)−1h(i)\ge h(i-1)-1h(i)≥h(i−1)−1 123...
2021-12-02
【CF554A Kyoya and Photobooks】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15634024.html 题目链接 暴力是肯定可以的。所以这里讲 O(1)O(1)O(1)。 首先不考虑重复，则有 (∣s∣+1)×26(|s|+1)\times 26(∣s∣+1)×26 种可行方案。 然后重复的就是在一个字母的左右放和这个字母相同的字母，有 ∣s∣|s|∣s∣ 种可能。 所以总共有 (∣s∣+1)×26−∣s∣(|s|+1)\times 26-|s|(∣s∣+1)×26−∣s∣ 种可能。 Code 12345678910111...
2021-11-15
【洛谷P1379 八数码难题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558545.html 题目链接 和atc之前的一道题类似，都是暴力广搜+记录状态。 从开始状态开始广搜，然后直接拿个map或者哈希记录状态即可。 时间复杂度为: O(9!)O(9!)O(9!)，因为最多也只有这么多种状态。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// ...
2022-01-08
【ZR #540. 【19普转提4】串串】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778576.html 题目链接 题目 给定两个长度为 nnn 的只包含’a’,‘b’,'c’的字符串s,ts,ts,t。 请打乱串 sss，使得 ∀i,si≠ti\forall i,s_i \not= t_i∀i,si=ti，且 sss 字典序最小。 思路 对于 ttt 串中从前往后每一个字母，在 sss 的剩余可选字母中选字典序最小的。 如果 sss 的剩余字母中没了，就往前找第一个可以替换的替换。 最后再对每种 ttt 中的字母按...
2023-10-25
SA+ST表维护height+单调队列维护：CF1073G
SA+ST表维护height+单调队列维护：CF1073G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134043286 https://www.luogu.com.cn/problem/CF1073G lcp相关的，先跑个sa，然后height建个ST表 现在考虑询问，我们按A和B按 rkrkrk 排序。现在考虑B->A，反过来同理。 我们可以用单调队列维护，满足height是单增的。因为越往前lcp必然越短。同时要维护有多少个。然后对于当前后缀...
2026-07-09
字符串进阶算法 1 ：exKMP、SA、SAM、后缀平衡树
字符串进阶算法 1 ：exKMP、SA、SAM、后缀平衡树 exKMP / Z函数 对于字符串 sss 的每个后缀，求其与 sss 的最长公共前缀 ziz_izi 要求 O(n)O(n)O(n) 我们考虑当前在对 iii 进行操作。 之前已经有一段区间 [l,r][l,r][l,r] 满足 s[1,r−l+1]=s[l,r]s[1,r-l+1]=s[l, r]s[1,r−l+1]=s[l,r]，且 rrr 最大。 若 i≤ri\le ri≤r，则直接继承 zi=zi−l+1z_i=z_{i - l + 1}zi=zi−l+1 接下来暴力匹配，只要匹配成功，此时 rrr...