题解 P3804 【【模板】后缀自动机】
cosmicAC
2018-11-21 09:23:32
本蒟蒻来发一篇后缀数组+并查集的题解。
如果做过[P2178](https://www.luogu.org/problemnew/show/P2178)，会发现此题和那题差不多，只是可能需要一丁点的卡常。
具体做法：先倍增求出后缀数组（这里不要试图写两个log的sort，会T到飞起），求height。然后把height从大到小排序，用并查集维护lcp长度$\geq$当前height的后缀组成的联通块，每次合并时尝试更新答案。
时间复杂度$O(n\log{n})$。如果使用DC3算法构建后缀数组，并使用基数排序的话是$O(n\alpha{n})$。
较简短的C++11代码如下：
```cpp
#include<bits/stdc++.h>
#define int64 long long
using namespace std;
char s[1<<20];int64 ans;
int n,sa[1<<20],rnk[1<<21],tp[1<<20],h[1<<20],c[1<<20],y='z',siz[1<<20],fa[1<<20];
void tsort(int i){
memset(c,0,sizeof c);int p=0;
for(int j=1;j<=i;j++)tp[++p]=n-i+j;
for(int j=1;j<=n;j++)
c[rnk[j]]++,sa[j]>i&&(tp[++p]=sa[j]-i);
for(int j=1;j<=y;j++)c[j]+=c[j-1];
for(int j=n;j;j--)sa[c[rnk[tp[j]]]--]=tp[j];
}
int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;i++)sa[i]=i,rnk[i]=s[i];
tsort(0);
for(int i=1;i==1 || y<n;i<<=1){
tsort(i);y=0;
for(int j=1;j<=n;tp[sa[j++]]=y)
y+=rnk[sa[j]]!=rnk[sa[j-1]]||rnk[sa[j]+i]!=rnk[sa[j-1]+i];
memcpy(rnk,tp,sizeof tp);
}
for(int i=1,k=0;i<=n;i++){
if(k)--k;
while(s[i+k]==s[sa[rnk[i]-1]+k])k++;
h[rnk[i]]=k;tp[i]=i;
}
sort(tp+1,tp+1+n,[](int a,int b){return h[a]>h[b];});
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
for(int i=1;i<n;i++)if(h[tp[i]]){
ans=max(ans,1ll*(siz[getf(tp[i]-1)]+=siz[getf(tp[i])])*h[tp[i]]);
fa[fa[tp[i]]]=fa[tp[i]-1];
}
printf("%lld\n",ans);
return 0;
}
```