洛谷P3804 【模板】后缀自动机

abab

4

#include<cstdio>
#include<cstring>
#include<vector>
#define LL long long 
using namespace std;
const int MAXN = 2 * 1e6 + 10;
char s[MAXN];
int N;
int last = 1, root = 1, tot = 1, fa[MAXN], ch[MAXN][26], len[MAXN], siz[MAXN];
void insert(int x) {
    int now = ++tot, pre = last; last = now;
    //last代表全串的点 
    len[now] = len[pre] + 1; siz[now] = 1;
    for(; pre && !ch[pre][x]; pre = fa[pre]) 
        ch[pre][x] = now;
    if(!pre) fa[now] = root;
    else {
        int q = ch[pre][x];//q是pre的祖先 pre -> q
        //说明pre有一条x转移边 q = pre + x
        if(len[q] == len[pre] + 1) fa[now] = q;
        //说明right集合完全重合，此时pre一定是now的后缀??
        else {//right集合不完全重合 
            int nows = ++tot; len[nows] = len[pre] + 1;
            memcpy(ch[nows], ch[q], sizeof(ch[q])); 
            fa[nows] = fa[q]; fa[q] = fa[now] = nows;
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows; 
        } 
    }
}
vector<int> v[MAXN];
LL ans = 0;
void dfs(int x) {
    for(int i = 0; i < v[x].size(); i++)
        dfs(v[x][i]), siz[x] += siz[v[x][i]];
    if(siz[x] > 1) ans = max(ans, 1ll * siz[x] * len[x]);
}

int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    scanf("%s", s + 1);
    N = strlen(s + 1);
    for(int i = 1; i <= N; i++) insert(s[i] - 'a');
    for(int i = 2; i <= tot; i++) v[fa[i]].push_back(i);
    dfs(root);
    printf("%lld", ans);
    return 0;
}