manacher算法一图复习
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16555504.html
本博客所有文章除特别声明外，均采用 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 奇...
2022-01-16
【P6739 [BalticOI 2014 Day1] Three Friends】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15809039.html 题目链接 题目 有一个字符串 SSS，对他进行操作： 将 SSS 复制为两份，存在字符串 TTT 中 在 TTT 的某一位置上插入一个字符，得到字符串 UUU 现在给定 UUU，求 SSS。 思路 哈希 先预处理这个字符串的哈希前缀和，然后枚举插入位置，这时候把左右的 SSS 求出来，看看是否相同。 需要注意的是，题目是说 SSS 不是唯一的猜输出 NOT UNIQUE，也就是说如果有多种切断方式但 SSS 一样还是...
2022-01-16
【P3538 [POI2012]OKR-A Horrible Poem】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15810272.html 题目 原题来自：POI 2012 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。 如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。 思路 首先，我们如果有三点： 一个字符串的循环节必然是字符串长度的约数 循环节的倍数如果长度还是字符串长度的约数，那么他也是循环节 如果一个长度 iii 是字符串循环节长度，那么 [l,r−i][l, r-i]...
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 中第...
2023-12-21
周期引理 PL (Periodicity Lemma.)
周期引理 PL (Periodicity Lemma.) 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121747 原先串：若干 ppp ，加一个前缀，因此是 A(x)1−xp mod xn+1\dfrac {A(x)}{1-x^p}\bmod x^{n+1}1−xpA(x)modxn+1 这个： mod xn+1\bmod x^{n+1}modxn+1 为0。（多项式） 我们有 R(x) mod xn+1=0,deg(R)∈nR(x...
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...
