题解 P4987 【回文项链】
command_block
2018-11-08 17:01:37
[安利Blog](https://www.luogu.org/blog/command-block/)
------------
### 如此妙 ~~模板~~ 的一道题怎么能没有题解呢?
看到“回文串”,“环”等字眼,直接上**manacher+拆环**乱搞,结果WA,拿了60pts。
后来仔细看了看题面:
我们定义回文串为环上一个**首尾不重叠**的连续子串(即环上每个结点最多被使用一次),且满足存在一个回文中心$i$,使得$i$之前的若干个字符分别与其关于$i$中心对称的字符相同。
对于$100\%$的数据,$n<=10^6$ ,$0<l<=n$**且$l$为奇数**。
### 只有奇回文串才算数呐!
manacher算法没听说过的,右转此题
https://www.luogu.org/problemnew/show/P3805
这题的拆环有些特殊,要把原字符串复制三遍。
不用插‘#’字符跑manacher,然后取**中间那一段**的回文延伸数组和$l$比较。
至于“环上每个结点最多被使用一次”这个要求,**不用理会**(自己想为什么)。
------------
~~丑陋的~~ 超短的AC代码。
```cpp
#include<iostream>
#include<cstdio>
using namespace std
int n,k,maxr,p,h[2005000],ans
char s[3005000]
int main()
{
scanf("%d%d%s",&n,&k,s+1)
for (int i=1 i<=n i++)s[n+n+i]=s[n+i]=s[i]
n*=3
for (int i=1 i<=n i++){
if (maxr>i)
h[i]=min(maxr-i,p-i+p>0 ? h[p-i+p] : 0)
else h[i]=1
while(i+h[i]<=n&&i-h[i]>0&&
s[i-h[i]]==s[i+h[i]])h[i]++
if (i+h[i]>maxr){maxr=i+h[i] p=i }
}for(int i=n/3+1 i<=n/3*2 i++)
if (h[i]*2-1>=k)ans++
printf("%d",ans)
return 0
}
//分号已删,做了魔改,不影响阅读
//减少代码复制,共建美好洛谷~
```