本文共 1216 字，大约阅读时间需要 4 分钟。

直接建回文树,得到以$i$结尾/开始的最大回文串长度

然后枚举分割点$O(n)$取$max$即可

比较模板的题

#include 
   
    using namespace std;const int maxn = 4e5+10;struct PAM{
   	int fail[maxn],zi[maxn][27],len[maxn],id,las;	int pre[maxn],suf[maxn],qui[maxn];//[1,i]结束 	char a[maxn];	PAM()	{
   		fail[0] = 1, fail[1] = 1; len[0] = 0, len[1] = -1;		las = id = 1;	}	int get_fail(int u,int index)	{
   		while( a[index]!=a[index-1-len[u]] )	u = fail[u];		return u;	}	void insert(int c,int index)	{
   		int u = get_fail(las,index);		if( zi[u][c]==0 )		{
   			int newnode = ++id, v = get_fail( fail[u],index);			len[newnode] = len[u]+2;			pre[index] = max( pre[index],len[newnode] );			suf[index-len[newnode]+1] = max( suf[index-len[newnode]+1],len[newnode] );			fail[newnode] = zi[v][c], zi[u][c] = newnode;		}		las = zi[u][c];	}	void solve()	{
   		cin >> ( a+1 ); int n = strlen( a+1 );		for(int i=1;i<=n;i++)	insert( a[i]-'a',i );		int ans = 0;		for(int i=1;i<=n;i++)	pre[i] = max( pre[i],1 ),suf[i] = max( suf[i],1 );		for(int i=1;i<=n;i++)	pre[i] = max( pre[i],pre[i-1] );		for(int i=n;i>=1;i--)	suf[i] = max( suf[i],suf[i+1] );		for(int i=2;i<=n;i++)	ans = max( ans,pre[i-1]+suf[i] );		cout << ans;	}}pam;int main(){
   	pam.solve();}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114602801 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！