弱周期定理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...
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 中第...
2022-06-11
牛客小白月赛28VP总结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16366208.html 牛客小白月赛28VP总结 比赛地址 A 数学题，快速幂+逆元即可 B 结论题，判断 xxx 与 yyy 模3余数 C 经典字符串括号题，用栈维护 D 抓住位运算的性质，判断 x−2yx-2yx−2y & yyy 的结果。 E 没做，但感觉应该就是个大线段树 F 也没做，应该就是先求所有一次函数的交点，然后维护最小和次小值 G KMP模板 H 最短路模板 I 把每个格子拆除1e4+7个，然后递推 J 并查集维护同种...
2026-06-17
算法复键——AC自动机
算法复键——AC自动机 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162074359 什么是AC自动机： 在Trie上跑kmp 核心思想：构建fail树。fail[u]指向一个节点，表示这个节点具有和u所在节点所代表串的最长公共后缀。 核心代码： 12345678910111213141516171819void bfs() { int i, j; q.push(1); fail[1] = 0; fail[0] = 1; // 根节点失配指向...
2022-01-12
【Loj #10051. 「一本通 2.3 例 3」Nikitosh 和异或】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15791222.html 题目链接 题目 给定一个含 NNN 个元素的数组 AAA，下标从 111 开始。请找出下面式子的最大值： (A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])(A[l_1]⨁A[l_1+1]⨁…⨁A[r_1])+(A[l_2]⨁A[l_2+1]…⨁A[r_2])(A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])，其中 1≤l1≤...
2023-12-21
broder剃头去尾的新broder
broder剃头去尾的新broder 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135122233 若红色为1串的broder，则显然黄串为2串的broder 因此broder在剃头去尾 可以用于均摊分析 题目：POI2012」Prefixuffix