【BZOJ】3676: [Apio2014]回文串
标签：first 开始 rom max 连接 while 字符串 字符 std
【题意】给定只含小写字母的字符串s，定义价值为回文子串的长度*出现次数，求最大价值。n
【算法】回文树
【题解】回文树上一个点的被访问次数是其作为最长回文子串的出现次数。
将fail边反向连接建树后，每个点的子树访问次数和就是这个回文子串的出现次数，可以dfs解决。
注意：要从-1点开始dfs才能保证到达所有点。记得开long long。
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=600010;
int n,tot,len[maxn],fail[maxn],length,sz,nownode,ch[maxn][30],first[maxn],size[maxn];
ll ans=0;
struct edge{int v,from;}e[maxn];
char s[maxn];
int getfail(int x){while(s[length-len[x]-1]!=s[length])x=fail[x];return x;}
void build(){
int y=s[++length]-‘a‘;
int x=getfail(nownode);
if(!ch[x][y]){
len[++sz]=len[x]+2;
fail[sz]=ch[getfail(fail[x])][y];
ch[x][y]=sz;
}
size[ch[x][y]]++;
nownode=ch[x][y];
}
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
int dfs(int x){
ll sum=size[x];
for(int i=first[x];i;i=e[i].from){
sum+=dfs(e[i].v);
}
ans=max(ans,sum*len[x]);
return sum;
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
len[0]=0;fail[0]=1;
len[1]=-1;fail[1]=1;
length=0;
sz=1;//!!!
for(int i=1;i)build();
insert(1,0);
for(int i=2;i){
insert(fail[i],i);
}
dfs(1);//1
printf("%lld",ans);
return 0;
}
View Code
【BZOJ】3676: [Apio2014]回文串
标签：first 开始 rom max 连接 while 字符串 字符 std
原文地址：http://www.cnblogs.com/onioncyc/p/6950869.html
评论