后缀数组&manacher

# 后缀数组 ## 前置芝士 [后缀数组 1](https://www.cnblogs.com/lykkk/p/10520070.html) [后缀数组 2](https://www.cnblogs.com/victorique/p/8480093.html) [后缀数组 3](https://www.luogu.com.cn/blog/luckyblock/post-bi-ji-hou-zhui-shuo-zu) ## 例题略解 #### [P2463 [SDOI2008]Sandy的卡片](https://www.luogu.com.cn/problem/P2463) 板子题。。。 然而我还是不会。 大概做法就是先把所有的串差分后拼成一个大的串，小的串之间用一个极大数(比差分数组中最大的数大就可以)隔开。 并且确保每个用于隔开小串的数大小不同，每隔开一个$+1$就可以了。 然后进行二分答案就$OK$了 [$code$](https://www.luogu.com.cn/paste/go4wliju) #### [P2336 [SCOI2012]喵星球上的点名](https://www.luogu.com.cn/problem/P2336) **SA+莫队** 大概就是像上一个题一样，将所有的名字建成一个大串，记录一下所在名字， 然后对于每个询问预处理一下在SA数组左右的端点 之后的做法和莫队就是标准的莫队了。。。 [$code$](https://www.luogu.com.cn/paste/d17rewwy) #### [P4094 [HEOI2016/TJOI2016]字符串](https://www.luogu.com.cn/problem/P4094) 正解：**主席树+SA+二分+RMQ** 但是**暴力**做法远快于正解，而且码量思路也比较好想 还是那个推论2，对于以a到b开始的每个后缀都求一下， 然后在把推算结果与d-c+1取最小值。 * 对于a到b中rk**小于**rk[c]的： 从rk[c]开始，到height[i]小于ans就停止，如果i大于sa[a]小于sa[b]更新就好了 * 对于a到b中rk**等于**rk[c]的： 特判一下 * 对于a到b中rk**大于**rk[c]的： 把小于rk[c]的操作从rk[c]+1到n进行一边就好了 [$code$](https://www.luogu.com.cn/paste/w40myr1t) #### [P4248 [AHOI2013]差异](https://www.luogu.com.cn/problem/P4248) **单调栈+SA求LCP** 比较易懂，大概就是先把题面上的式子简化一下， 变成某个带n的代数式加上LCP $∀1\leq i<j\leq n,$ $LCP(sa_i,sa_j)=\min\limits_{i< k\leq j}$ ${$ $height_k$ $}$ 然后运用LCP的推论2，将问题转化成了求每个子区间的最小值的加和 可以打权值线段树，但是太麻烦了，于是可以用**单调栈**来优化 * 注意： 在求SA时M所赋的初值应大于原序列中的最大值 [$code$](https://www.luogu.com.cn/paste/87t2p3m3) #### [BZOJ3230](https://www.luogu.com.cn/problem/U162799) **SA+RMQ(ST表)+二分** 每个字串都是一个后缀的前缀，先求一下SA以及LCP， 然后就可以预处理出每个后缀的左右边界值 在处理询问的时候进行二分，查看要查询的字串的左右端点在哪两个后缀中， 最后算一下就好了 * 注意： 对于每一个操作都要搞正反两遍 [$code$](https://www.luogu.com.cn/paste/eiagomoy) #### [P2178 [NOI2015] 品酒大会](https://www.luogu.com.cn/problem/P2178) 常规做法是**并查集+SA(+set)** 但是zxb用三棵**线段树**硬是给干过去了，做法么，和**差异**这个题差不多，tql%%% 用RMQ**暴力**有两种打法： * 最简单的也是得分最低的： 每种情况都枚举一遍 * 优化的暴力：对于不同的LCP都更新，然后累加 **正解**就是对于第二种暴力放弃RMQ，改用并查集维护，处理一个siz值，对于不同的点进行合并，这里用**set**维护了一下并查集 * 注意：因为有负值，因此们要求max(最大值 * 次大值，最小值 * 次小值) [$code$](https://www.luogu.com.cn/paste/cfr64p8a) # $manacher$ ## 前置芝士 [$manacher$](https://www.cnblogs.com/fan1-happy/p/11166182.html) ## 例题略解 #### [P4287 [SHOI2011]双倍回文](https://www.luogu.com.cn/problem/P4287) 半个板子题，有一个很妙的思路，在处理manacher的时候整一下，对于i=1的情况，循环一下i+p[i]，如果j-i长度为4的倍数，更新答案。 毕竟，双倍的回文串还要计算上在每一位之间插进去的字符。 *** **荣登最优解**$Top3$ **** * 注意：i&3表示 $i\mod4$ ,同样的，i&7可以表示$i\mod8$ [$code$](https://www.luogu.com.cn/paste/g95hqr4v) #### [P4555 [国家集训队]最长双回文串](https://www.luogu.com.cn/problem/P4555) 我真傻，真的，我单知道输入字符串从0开始，却不知道求manachar时也要从0开始处理 和上一题差不多，都是在manachar函数里搞事情 开一个l和r数组用来表示以i为分割点的所谓双回文串的左右端点，理论上来讲，l在最后取max时应该从n到2，r应该从2到n，防止更改过的对以后的有影响。~~但是数据他水呀~~ 最后取一下$l[i]+r[i]$的最值就ok了 [$code$](https://www.luogu.com.cn/paste/l2w33312) #### [P3501 [POI2010]ANT-Antisymmetry](https://www.luogu.com.cn/problem/P3501) #### [SP15569 STC02 - Antisymmetry](https://www.luogu.com.cn/problem/SP15569) 还是在manachar的板子上进行修改。 观察题面，无非就是要求我们求**异或**意义下的回文串 因为题面的意思是要求我们1与0相对，而不是1与1相对，在函数里循环的时候两个两个的枚举防止#与#判等的情况，相对关系用一个to数组存就好了。 在一个长度为$L$的异或回文串里共有$\frac L2$个异或回文串，直接加起来就好了。 [$code$](https://www.luogu.com.cn/paste/j62ggkgp) #### [P2601 [ZJOI2009]对称的正方形](https://www.luogu.com.cn/problem/P2601) 正解和暴力都想了挺长时间，尤其是**暴力**[$code$](https://www.luogu.com.cn/paste/9jyjadmz) 用了**离散化，regster int，inline**来优化。 对于正解，就是对于整个方块横着竖着各扫一边，统计出横纵最长回文串的长度，在运算的时候可以用**单调队列**优化。 [$code$](https://www.luogu.com.cn/paste/v3nlre78)