P3804 【模板】后缀自动机

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

由于i在link[i]处断裂,所以两者的maxlen已经不同,所以我们要将断裂的点重新接上,也就是从link[i]向i建边,最后跑一边dfs统计答案即可。

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;
}

P3804 【模板】后缀自动机

原文：https://www.cnblogs.com/ukcxrtjr/p/11333849.html