[APIO2014]回文串

题意

给定一个字符串，求一个回文子串，使得它的长度×出现次数最大

思路

回文自动机

学了之后再来补坑qwq

---

后缀自动机SAM

参（zhao）考（ban）STO beretty 的博客

对原串建SAM，然后跑manacher，对于每个回文串，在SAM询问出现次数，求最大值即可

由于直接在SAM上面询问是O(n)的，这样做实际上是\(n^2\)的，于是考虑在parent树上倍增

记fa[ i ][ j ]为i节点向上跳\(2^j\)步后的位置，由于在parent树上的一个节点的父亲表示的串是这个节点表示的串的后缀，所以对于一个串[ L , R ]，从pos[ R ]这个节点开始向上跳，使得len>=R-L+1的最小节点即为所求，它的size数组即为出现次数

注意这道题fa数组不能开太大，否则会MLE

Code：

#include<bits/stdc++.h> #define N 600005 using namespace std; typedef long long ll; char a[N]; int n,ndsum=1,las=1,root=1; int sz[N],tot[N],rk[N],pos[N]; int len,p[N]; int fa[N][21]; ll ans=0; struct Node { int ch[26],par,len; }s[N]; void add_sam(int w,int i) { int x=++ndsum,tmp=las; sz[x]=1; pos[i]=x; s[x].len=s[tmp].len+1; for(;!s[tmp].ch[w];tmp=s[tmp].par) s[tmp].ch[w]=x; if(!tmp) s[x].par=root; else { int B=s[tmp].ch[w]; if(s[tmp].len+1==s[B].len) s[x].par=B; else { int nb=++ndsum; s[nb]=s[B]; s[nb].len=s[tmp].len+1; s[B].par=s[x].par=nb; for(;s[tmp].ch[w]==B;tmp=s[tmp].par) s[tmp].ch[w]=nb; } } las=x; } void manacher_init() { for(int i=n;i>=1;--i) a[i*2+1]='#',a[i*2]=a[i-1]; a[0]=a[1]='#'; len=2*n+2; } void manacher() { manacher_init(); int maxr=0,mid; for(int i=0;i<len;++i) { if(maxr>i) p[i]=min(maxr-i,p[(mid<<1)-i]); else p[i]=1; while(a[i+p[i]]==a[i-p[i]]) ++p[i]; if(i+p[i]-1>maxr) {maxr=i+p[i]-1;mid=i;} } } void init() { for(int i=1;i<=ndsum;++i) { int x=rk[i]; fa[x][0]=s[x].par; for(int j=1;j<=20;++j) fa[x][j]=fa[fa[x][j-1]][j-1]; } } int query(int l,int r) { int now=pos[r]; for(int i=20;i>=0;--i) if(s[fa[now][i]].len>=r-l+1) now=fa[now][i]; return sz[now]; } int main() { scanf("%s",a); n=strlen(a); for(int i=0;i<n;++i) add_sam(a[i]-'a',i); manacher(); for(int i=1;i<=ndsum;++i) tot[s[i].len]++; for(int i=1;i<=ndsum;++i) tot[i]+=tot[i-1]; for(int i=1;i<=ndsum;++i) rk[tot[s[i].len]--]=i; for(int i=ndsum;i>=1;--i) sz[s[rk[i]].par]+=sz[rk[i]]; sz[1]=0; init(); for(int i=2;i<len;i+=2) { int x=(i>>1)-1,half=(p[i]>>1)-1; ans=max(ans,(ll)(p[i]-1)*query(x-half,x+half)); } for(int i=3;i<len;i+=2) { int x=((i-1)>>1)-1,half=(p[i]-1)>>1; ans=max(ans,(ll)(p[i]-1)*query(x-half+1,x+half)); } cout<<ans<<endl; return 0; }

转载于:https://www.cnblogs.com/Chtholly/p/11326231.html