[模板] 后缀自动机

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 1000010;

vector<int> tree[maxn*2];

typedef long long ll;

char s[maxn];
int n, tot, last = 0;
ll ans = 0;
int tr[maxn*2][26], par[maxn*2], len[maxn*2], sum[maxn*2], val[maxn*2];

void (int c, int l) {
    int np = ++tot; len[np] = l; val[np] = 1;
    while (!tr[last][c]) {
        tr[last][c] = np;
        last = par[last];
    }
    if (!last) par[np] = 1;
    else {
        int q = tr[last][c];
        if (len[q] == len[last] + 1) {
            par[np] = q;
        } else {
            int nq = ++tot;
            len[nq] = len[last] + 1;
            par[nq] = par[q];
            memcpy(tr[nq], tr[q], sizeof(tr[nq]));
            par[q] = par[np] = nq;
            while (tr[last][c] == q) {
                tr[last][c] = nq;
                last = par[last];
            }
        }
    }
    last = np;
}

void dfs(int u) {
    sum[u] = val[u];
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i];
        dfs(v);
        sum[u] += sum[v];
    }
}

int main() {
    scanf("%s", s+1);
    n = int(strlen(s+1));
    last = ++tot;
    for (int i = 1; i <= n; i++) {
        addchar(s[i]-'a', i);
    }
    for (int i = 2; i <= tot; i++) tree[par[i]].push_back(i);
    dfs(1);
    for (int i = 2; i <= tot; i++) if (sum[i] > 1) ans = max(ans, 1LL*sum[i]*len[i]);
    printf("%lldn", ans); 
    return 0;
}