BZOJ 3672如何通过回文树解决回文串问题？

本文共计886个文字，预计阅读时间需要4分钟。

为了找到包含小写字母s的字符串s中，所有子字符串中出现次数乘以长度的最大值，我们可以遍历字符串s中的每个位置，对于每个位置，我们尝试以该位置为中心向两边扩展，检查以该位置为中心的子字符串中s的出现次数和长度，并更新最大值。

以下是实现这一功能的Python代码：

pythondef max_value_with_s(s): n=len(s) max_value=0 max_length=0 max_substring=

for i in range(n): count=0 length=0 left=i right=i

# 向左扩展 while left >=0 and s[left]=='s': count +=1 left -=1 length +=1

# 向右扩展 while right

# 更新最大值 current_value=count * length if current_value > max_value or (current_value==max_value and length > max_length): max_value=current_value max_length=length max_substring=s[left + 1:right]

return max_value, max_substring

示例s=absssssscdsdemax_value, max_substring=max_value_with_s(s)print(f最大值: {max_value}, 子字符串: '{max_substring}')

这段代码会输出包含小写字母s的字符串s中，所有子字符串中出现次数乘以长度的最大值以及对应的子字符串。

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。 字符串长度≤300000

回文树模板题

建立回文树，则每个节点对应了一个本质不同的回文串，出现次数为cnti
于是暴力遍历即可

一个长度为n的字符串本质不同的回文串最多有n个。

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define MAXN (600000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}

namespace Palindromic_Tree {
int s[MAXN],n;
int tot,next[MAXN][26],link[MAXN],len[MAXN],last;
int cnt[MAXN];

int newnode(int l)
{
len[tot]=l;
return tot++;
}
void mem() {
MEM(s) MEM(next) MEM(link) MEM(len) MEM(cnt)
n=tot=0;
newnode(0); newnode(-1);
link[0]=link[1]=1; s[0]=27;
last=0;
}

int getnode(int x)
{
while (s[ n - len[x]-1 ] != s[n] ) x=link[x];
return x;
}

void add(int c) {
s[++n]=c;
// cout<<"1";
int cur=getnode(last);
if (!next[cur][c])
{
int now=newnode(len[cur]+2);
int tmp=getnode(link[cur]);
link[now]=next[tmp][c];
next[cur][c] = now;

}
last=next[cur][c];
cnt[last]++;
}

void work()
{
RepD(i,tot) cnt[link[i]]+=cnt[i];

ll ans=0;
Fork(i,2,tot) {
ans=max(ans,1LL*cnt[i]*len[i]);

}
cout<<ans<<endl;

}

}
using namespace Palindromic_Tree;

char S[MAXN];
int N;
int main()
{
// freopen("bzoj3676.in","r",stdin);
// freopen(".out","w",stdout);

Palindromic_Tree::mem();

scanf("%s",S);
int N=strlen(S);
Rep(i,N) Palindromic_Tree::add(S[i]-'a');

Palindromic_Tree::work();

return 0;
}