6
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> UPD1.8，更新了一道例题
太好啦！加精啦！\tiny太好啦！加精啦！太好啦！加精啦！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以下为正文。
> 字符串的70%可以用哈希+二分解决，而剩下30%中的70%可以用后缀数组解决。
标题险些打不下
如你所见，本文讲解两种算法：最小表示法& Manacher\tt {Manacher}Manacher 算法（俗称马拉车）。
PART 1.最小表示法
前置芝士：循环同构
定义：当字符串 SSS 中可以选定一个位置 iii 满足
S[i⋯n]+S[1⋯i−1]=TS[i\cdots n]+S[1\cdots i-1]=T S[i⋯n]+S[1⋯i−1]=T
则称 SSS 和 TTT 循环同构。
最小表示法
定义：字符串 SSS 的最小表示为与 SSS 循环同构的所有字符串中字典序最小的字符串。
人话：把 SSS 放在一个环上，从任一点开始读取字符串，所得的串中字典序最小的即为 SSS 的最小表示。
暴力算法
思维难度： 000
我们每次比较 iii 和 jjj 开始的循环同构，把当前比较到的位置记作 kkk ，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解。
* 缺点
该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉。
例如：对于字符串 aaa⋯abaaa\cdots abaaa⋯ab ，不难发现这个算法的复杂度退化为 O(n2)O(n^2)O(n2) 。
优化算法
我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程。
考虑字符串 AAA 、 BBB 为 SSS 的两组循环同构，且他们的前 kkk 个字符相等，即：
S[i⋯i+k−1]=S[j⋯j+k−1]S[i\cdots i+k-1]=S[j\cdots j+k-1] S[i⋯i+k−1]=S[j⋯j+k−1]
不妨设 S[i+k]>S[j+k]S[i+k]>S[j+k]S[i+k]>S[j+k]
如图，不难发现对于任意起始点为 l(i≤l≤i+k)l(i\leq l\leq i+k)l(i≤l≤i+k) 的字符串不可能成为答案（必定碰到红框导致被否掉）。
（黑框部分为相等部分）
所以我们比较时可以跳过下标 l∈[i,i+k]l\in [i,i+k]l∈[i,i+k] ，直接比较 Si+k***_{i+k****i+k+1 。
算法流程
(1)(1)(1) 初始化指针 i=0,j=1i=0,j=1i=0,j=1 ，匹配长度 k=0k=0k=0。
(2)(2)(2) 比较第 kkk 位，根据比较结果跳转指针（哪个大跳哪个）。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同。
(3)(3)(3) 重复 (2)(2)(2) 直到结束。
(4)(4)(4) 从 min(i,j)min(i,j)min(i,j) 开始输出答案。
具体体细节见代码。
例题1
板子题，直接上代码。
例题2
还是板子题，直接把最小表示丢进set里。
code:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 2.MANACHER\TT MANACHERMANACHER算法
引入
我们来看这样一个问题：求一个字符串的最长回文子串。
暴力
非常简单，枚举每个子串，判断回文，时间复杂度 O(n3)O(n^3)O(n3)。
中心扩展法
枚举每个点，向两边扩展，时间复杂度 O(n2)O(n^2)O(n2)。
需要注意的是，这个算法只能判断奇数长度的回文。
解决办法也很简单，在每个字符后面插入一个空格，把偶回文转换为奇回文。
优化(MANACHER\TT {MANACHER}MANACHER)
我们考虑以下定义
p[i]p[i]p[i]：表示以位置iii为中心的最大回文半径。
ididid：当前已知的右边界最靠右的回文中心。
mxmxmx：该回文的最右边界索引，满足 mx=id+p[id]−1mx=id+p[id]-1mx=id+p[id]−1。
算法流程(具体细节见代码注释)
* 遍历每个位置 iii ，首先利用对称性确定 p[i]p[i]p[i] 的初始值：
如果 iii 在当前最右回文边界mxmxmx之外，只能从111开始暴力扩展。
如果 iii 在 mxmxmx 之内，可以通过对称点 i1i_1i1 （ iii 关于 ididid 的对称点）的信息，取 min(mx−i,p[i1])min(mx-i, p[i_1])min(mx−i,p[i1 ]) 作为初始值。
* 确定初始值后，向两边扩展检查字符是否匹配，更新回文半径:
如果当前回文的右边界超过了 mxmxmx ，则更新 ididid 和 mxmxmx 。
时间&空间复杂度
均为 O(n)O(n)O(n)，十分优秀。
例题1
这道题的主要思路就是马拉车+快速幂。
code:
例题2
这是一道比较难的题。
先预告一下：这道题中有一个技巧：在原串中插入字符后再在头尾各插一个别的字符充当边界。
接下来，题解开始：
我们处理出每个回文串的左右边界 ll[i]ll[i]ll[i]、rr[i]rr[i]rr[i]。
那么不难发现有：
ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1)ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)\\ rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1) ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1)
（这段可以自己画画图）
跑完 Manacher\tt {Manacher}Manacher 后，我们求出每个'#'为断点的 ll[i]ll[i]ll[i] 和 rr[i]rr[i]rr[i] ，其中 rr[i]rr[i]rr[i] 因为是 iii 结尾的回文长度，所以直接顺推，每往后移一位，最长回文子串长度 −2-2−2 ，于是 rr[i]=max(rr[i],rr[i−2]−2)rr[i]=max(rr[i],rr[i−2]−2)rr[i]=max(rr[i],rr[i−2]−2) ( i−2i−2i−2 是上一个'#'位置)，同理 ll[i]ll[i]ll[i] 直接逆推：
ll[i]=max(ll[i],ll[i+2]−2)ll[i]=max(ll[i],ll[i+2]−2)ll[i]=max(ll[i],ll[i+2]−2) 。
最后枚举每个'#'为断点，更新答案即可
code:
例题3
如你所见，这是一道紫题，吓哭了。
但是我和题解区的一位大佬想到了同一个解法：
直接枚举一下每个处理出的回文是不是两段一样的回文相加不就好了？
具体实现：在 Manacher\tt {Manacher}Manacher 中 mxmxmx 更新时,判断所有新出现的回文串的前一半是否为回文串即可。。。
然后就……
code:
嗯
例题4
这题洛谷上没找到，我觉得是紫
大致思路：Manacher\tt ManacherManacher+贪心区间覆盖
code：
留道拓展题吧
你猜为啥是拓展题，因为我也不会。
谁做出来了私信一下我哈。
孩子们我们没救了！题解区怎么全是FFT啊吓哭了
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
完结撒花！
四蓝三紫，不知道要吓哭多少人\TINY 四蓝三紫，不知道要吓哭多少人四蓝三紫，不知道要吓哭多少人
有帮助，赞一个