「Luogu P4987」回文项链解题报告

题面

求环中的长度为k（k为奇数）且回文中心不同的回文串个数

思路：

刚学manacher算法，就送上一道模板题，此题注重对manacher算法的理解

Manacher，但是不用插入其他符号，因为k是奇数，中心一定在字符上

不知道Manacher？

洛谷日报上有讲，但是比较难懂，建议上B站更深入了解下\(\to\)

可以先把代码抄下来，然后一边看讲解一边理解代码含义，这样更能理解

反正我第一遍已经看蒙了

补充和纠正：

关于前几篇题解，一些小细节纠正一下

文末的代码更加简洁易懂

1、这是一个环，要做Manacher就应该拆环为链，第一篇题解说：应该重复复制三次（扩展为原来的三倍），但是实际上两次（扩展为原来的两倍）就够了

2、p数组（p[i]）表示的是以i为中心的最长回文串的半径（包括i这个字符），原本的Manacher算法因为加入的额外的#号，而是p[i]表示的是就是原本最长回文串的长度+1，因此求Ans的时候应该用p[i]-1，但是现在我们不加#号了，p[i]表示的就是以i为中心的最长回文串的半径，此时长度就应该表示为p[i]*2-1，意思是半径*2-回文中心重复计算的字符

Code：

#include<bits/stdc++.h>

#define N 1000010//N<<1表示长度扩展为原来的两倍

using namespace std;

int n,k,p[N<<1],ans,res;

char s[N<<1];

void manacher()//标准的Manacher算法，就是没有加'#'号，而且起点为1

{

	s[0]='?';

	s[2*n+1]='!';

	int id=0,mx=0;//id表示目前最长回文串的中心，mx则是右边界

	for(int i=1;i<=2*n;i++)

	{

		if(i<mx)

			p[i]=min(p[2*id-i],mx-i);//如果中心在mx范围内，用mx去更新p[i]

		else

			p[i]=1;

		while(s[i-p[i]]==s[i+p[i]])//然后暴力

			p[i]++;

		if(mx<i+p[i])//更新mx和id

		{

			id=i;

			mx=i+p[i];

		}

	}

	return;

}

int main()

{

	int i;

	scanf("%d%d",&n,&k);

	scanf("%s",s+1);

	for(i=1;i<=n;i++)//复制

		s[i+n]=s[i];

	manacher();//跑一遍Manacher

	res=(k+1)>>1;//表示起始的中心i的位置，这个位置是第一个有可能长度为k的回文串的中心（串s[1-k]的中心）

	for(i=res;i<=res+n-1;i++)//对于每一个点遍历一次，所以是res+n-1

		if(p[i]*2-1>=k)//真正的长度只要大于等于k就是可以的（大于k的可以把他砍成k啊~）

			ans++;

	printf("%d",ans);

	return 0;

}

巴特西

「Luogu P4987」回文项链解题报告

题面

思路：

Manacher，但是不用插入其他符号，因为k是奇数，中心一定在字符上

补充和纠正：

推荐题目：

最新文章

热门文章

巴特西

「Luogu P4987」回文项链 解题报告

题面

思路：

Manacher，但是不用插入其他符号，因为k是奇数，中心一定在字符上

补充和纠正：

推荐题目：

最新文章

热门文章

「Luogu P4987」回文项链解题报告