manacher – Tgotp-Blog

3790: 神奇项链

容易发现,处理回文串的时候得到的答案是可以去更新答案的,
即 令 f[i] 表示处理前 i 个最小由几个回文串构成,
那么,对于第i个位置,他由 [i-p[i],n]能更新的就是 前  [1,i+p[i]-1]
因为前后缀相同能直接放在一起,容易正确[......]

Read more

3676: [Apio2014]回文串

卡着时限过的…
时间大概是垫底一般的存在把…
容易想到马拉车处理回文串(不过这题大佬都是回文自动机啥的。。。
然后考虑相同的串一定是sa上h数组连续的一段,那么二分左右端点即可.
然后扫一遍就求出了答案
c++代码如下:

[......]

Read more

2342: [Shoi2011]双倍回文

并查集 + manacher

看到回文串很容易想到了马拉车

首先发现双倍回文既然是4得倍数,那么其中心一定是添加得符号。

同样,他的一半得中心也一样是添加得符号。

考虑枚举双倍回文中心。

先处理出他的回文串长度,因为其左右对称,那么只用考虑他的左边最长回文串长度。[......]

Read more

2084: [Poi2010]Antisymmetry

manacher 裸题。

令 0 = 1 跑马拉车就好了。

c++代码如下:

 

hdu3068 && Luogu 3805 manacher 模板

模板题。