broder剃头去尾的新broder
broder剃头去尾的新broder
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135122233
若红色为1串的broder，则显然黄串为2串的broder
因此broder在剃头去尾
可以用于均摊分析
题目：POI2012」Prefixuffix
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-14
manacher 算法总结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551651.html 测试一下这个博客园的功能（图片好像只能在洛谷上看，有时间就改） manacher 算法总结 题目大意 给定一字符串，求其最长回文串长度 方法对比 暴力效率：O(n3)O(n^3)O(n3)，优化后为O(n2)O(n^2)O(n2) manacher效率：O(n)O(n)O(n) 算法思想 回文串有两种：奇回文与偶回文 分类讨论太麻烦，主要是我不会，于是我们就统一为奇回文 如何统一 例： abbab 偶回文：abba 奇...
2021-11-15
【洛谷P1379 八数码难题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558545.html 题目链接 和atc之前的一道题类似，都是暴力广搜+记录状态。 从开始状态开始广搜，然后直接拿个map或者哈希记录状态即可。 时间复杂度为: O(9!)O(9!)O(9!)，因为最多也只有这么多种状态。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// ...
2026-08-16
CF2196E：SA的应用
CF2196E：SA的应用 首先贪心的思路是显然的，因此我们相当于在t串中不断求最长可错配lcp 法1：根号分治 我们考虑以 BBB 分块 Case1：对于 d≤Bd\le Bd≤B 的情况。（即一次最多走 ddd 步） 我们可以先预处理 sss 中所有小于等于 BBB 的子串，并枚举它的哪个位置是空的。接下来把这个串挖掉这个空直接丢入hash中（相当于我们枚举的这一位直接赋值为0），这样的复杂度是 O(nB2)O(nB^2)O(nB2) 的。 然后我们现在处理 ttt 串。我们可以枚举每一个被替换的位置 iii ，那么显然 iii 只有 BBB 种可能。然后我们再去枚举 ddd。...
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...
2023-12-21
弱周期定理WPL (Weak Periodicity Lemma.)
弱周期定理WPL (Weak Periodicity Lemma.) 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121712 因为 sis_isi 可以去到 si−p,si+q…s_{i-p},s_{i+q}\dotssi−p,si+q… ，因此可以表示成 ap−bqap-bqap−bq 的形式。 本质：划分等价类，等价类有一个迭代的过程，怎么都可以走到 gcd(p,q)\gcd(p,q)gcd(p,q) ，但走不到更小的
2022-01-17
【P4824 [USACO15FEB]Censoring S】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15812544.html 题目 Farmer John为他的奶牛们订阅了Good Hooveskeeping杂志，因此他们在谷仓等待挤奶期间，可以有足够的文章可供阅读。不幸的是，最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章，FJ不愿让他的奶牛们看到这些内容。 FJ已经根据杂志的所有文字，创建了一个字符串 SSS ( SSS 的长度保证不超过 10610^6106 )，他想删除其中的子串 TTT ,他将删去 SSS 中第...