【BZOJ2565】最长双回文串 Manacher

2022-12-30 12:00:27

【BZOJ2565】最长双回文串

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

HINT

样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
对于100%的数据，2≤|S|≤10^5

题解：网上好多题解都是回文树，回文自动机，感觉没有必要啊！直接上Manacher算法

由于双回文串是将两个回文串拼在一起得到，我们可以枚举中间的'*'点，预处理出以它结尾的最长回文串和以它开头的最长回文串，然后加在一起更新答案。由于求以它结尾的回文串和以它开头的回文串是互部影响的，我这里只说怎么求以它结尾的最长回文串，这里用ls[j]表示。

当我们用Manacher算法求出回文中心i的回文半径rl[i]后，那么在(i，i+rl[i])内的字符都可以用以i为中心的回文串来结尾，（就是说以i为中心的回文串能以(i,i+rl[i])内的字符结尾，以(i,i+rl[i])内字符结尾的最长回文串可能以i为中心）

但是我们不能用i一个一个更新以（i,i+rl[i]）内的字符结尾的最长回文串长度啊，但是我们发现，以i+rl[i]结尾的回文串长度为rl[i]-1（不算中间的'*'），以i+rl[i]-2结尾的回文串长度自然就是rl[i]-1-2（再说一遍，不算中间的'*'）。然后我们只需要从左到右扫一遍，令ls[i]=max(ls[i],ls[i-2]-2)就行啦！

感觉说了这么多也没有直接看代码简单明了

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

char s1[500010],str[1000010];

int n,len,rl[1000010],mx,pos,ls[1000010],rs[1000010],ans;

int main()

{

	scanf("%s",s1);

	int i;

	len=strlen(s1);

	for(i=0;i<len;i++)	str[n++]='*',str[n++]=s1[i];

	str[n++]='*';

	for(mx=-1,i=0;i<n;i++)

	{

		if(mx>i)	rl[i]=min(mx-i+1,rl[2*pos-i]);

		else	rl[i]=1;

		for(;i+rl[i]<n&&rl[i]<=i&&str[i+rl[i]]==str[i-rl[i]];rl[i]++);

		if(i+rl[i]-1>mx)	mx=i+rl[i]-1,pos=i;

		rs[i-rl[i]+1]=max(rs[i-rl[i]+1],rl[i]-1);

		ls[i+rl[i]-1]=max(ls[i+rl[i]-1],rl[i]-1);

	}

	for(i=0;i<n;i+=2)	rs[i]=max(rs[i],rs[i-2]-2);

	for(i=n-1;i>=0;i-=2)	ls[i]=max(ls[i],ls[i+2]-2);

	for(i=0;i<n;i+=2)	if(ls[i]&&rs[i])	ans=max(ans,ls[i]+rs[i]);

	printf("%d",ans);

	return 0;

}

码农公寓