题意
给定一个字符串, 求一个回文子串, 使得它的长度 * 出现次数最大
思路
回文自动机
学了之后再来补坑 qwq
后缀自动机 SAM
参 (zhao) 考(ban)STO beretty 的博客 https://www.luogu.org/blog/beretty/solution-p3649
对原串建 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;
- }
[APIO2014]回文串
来源: http://www.bubuko.com/infodetail-3149343.html