manacher

算法原理

\(manacher\) 是根据前面已经求出的回文字符串的回文对称性质，而缩减当前位置求回文长度的时间。

\(j\) 因为 \(p_0\) 的回文性质，就可以通过 \(i\) 位置已经求好的回文长度，节省蓝色线段长度的时间。

例题

Luogu P3805 【模板】manacher 算法

因为有奇数长度的回文串，也有偶数长度的回文串，所以在相邻的字符中加入符号。

p[i]->当前位置的最大回文长度（不包括符号）

#include
#define maxn 100100001
using namespace std;
int p[maxn],pos,maxr;
char s[maxn],ss[maxn];
int ans=-1;
int n;
int main()
{
    ios::sync_with_stdio(false);
    cin>>s+1;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++) ss[i<<1]=s[i],ss[(i<<1)|1]='#';
    ss[0]='@';ss[1]='#';
    strcpy(s,ss);
    n=(n<<1)|1;
    for(int i=1;i<=n;i++)
    {
        if(imaxr) maxr=i+p[i],pos=i;
        ans=max(ans,p[i]);
     } 
     cout<


Luogu P4555 [国家集训队]最长双回文串
\(\quad\)这个题目就是在每对相邻的字符中间插入符号，以此为断点，求左边最大回文子串，右边最大回文子串，答案就是每一个端点的左右相加。

\(\quad\)注意：求出后要再次递推更新求解，因为之前只更新了当前的最大值，并不一定就是全局最优解。
#include
#define maxn 51110010
using namespace std;
char s[maxn],ss[maxn];
int p[maxn],maxr,pos,l[maxn],r[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin>>s+1;
	int n=strlen(s+1);
	for(int i=1;i<=n;i++) ss[(i<<1)]=s[i],ss[(i<<1)|1]='#';
	ss[0]='@';
	ss[1]='#';
	strcpy(s,ss);
	n=(n<<1)|1;
	for(int i=1;i<=n;i++)
	{
		if(imaxr) maxr=i+p[i],pos=i;
		l[i-p[i]]=max(l[i-p[i]],p[i]);
		r[i+p[i]]=max(r[i+p[i]],p[i]); 
	}
	int ans=0;
	for(int i=3;i<=n;i+=2) l[i]=max(l[i],l[i-2]-2);
	for(int i=n;i>=1;i-=2) r[i]=max(r[i],r[i+2]-2);
	for(int i=1;i<=n;i+=2)
	{
		if(r[i] && l[i])
		ans=max(r[i]+l[i],ans);
	}
	cout<

回文条件改变的回文串问题 Luogu P3501 [POI2010]ANT-Antisymmetry
\(\quad\)首先回文串一定要是偶数，其次对称条件改为两个字符相反即可。
#include
#define ll long long
#define maxn 10000100
using namespace std;
int n,p[maxn],maxr,pos;
char s[maxn],ss[maxn];
int main()
{
	cin>>n>>s+1;
	for(int i=1;i<=n;i++) ss[(i<<1)]=s[i],ss[(i<<1)|1]='#';
	ss[0]='@';
	ss[1]='#';
	strcpy(s,ss);
	n=(n<<1)|1;
	for(int i=1;i<=n;i+=2)
	{
		if(i0 && i+p[i]+1maxr) maxr=i+p[i],pos=i;
	}
	ll ans=0;
	for(int i=1;i<=n;i+=2)
	{
		ans+=(p[i]/2);
	}
	cout<

manacher

算法原理

例题

相关

标签