題面:https://www.luogu.org/problem/P3804

由于i在link[i]處斷裂,所以兩者的maxlen已經(jīng)不同,所以我們要將斷裂的點(diǎn)重新接上,也就是從link[i]向i建邊,最后跑一邊dfs統(tǒng)計(jì)答案即可。Code: #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<ctime> using namespace std; const int N=2000010,M=26; int Size=1,Last=1,trans[N][M],maxlen[N],link[N],head[N],cnt,len; long long sz[N],ans; char s[N]; struct Edge{int to,Next; }edge[N]; void add(int u,int v){++cnt;edge[cnt].to=v;edge[cnt].Next=head[u];head[u]=cnt; } void extend(int id){int cur=++Size,p;sz[Size]=1;maxlen[cur]=maxlen[Last]+1;for (p=Last;p&&!trans[p][id];p=link[p]){trans[p][id]=cur;}if(!p){link[cur]=1;}else{int q=trans[p][id];if(maxlen[q]==maxlen[p]+1){link[cur]=q;}else{int clone=++Size;maxlen[clone]=maxlen[p]+1;memcpy(trans[clone],trans[q],sizeof(trans[clone]));link[clone]=link[q];for(;p&&trans[p][id]==q;p=link[p]){trans[p][id]=clone;}link[cur]=link[q]=clone;}}Last=cur; } void dfs(int u){for(int i=head[u];i;i=edge[i].Next){int v=edge[i].to;dfs(v);sz[u]+=sz[v];}if(sz[u]!=1){ans=max(ans,sz[u]*maxlen[u]);} } int main(){scanf("%s",s);len=strlen(s);for(int i=0;i<len;i++){extend(s[i]-'a');}for(int i=2;i<=Size;i++){add(link[i],i);}dfs(1);printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ukcxrtjr/p/11333849.html

總結(jié)

以上是生活随笔為你收集整理的P3804 【模板】后缀自动机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。