1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include<bits/stdc++.h> #define LL long long using namespace std; const int N = 2e6 + 5; int n; int tot = 1, last = 1; struct Node{ int len, fa; int ch[26]; }node[N]; char str[N]; LL f[N]; LL ans; int idx; int e[N], ne[N], h[N]; void extend(int c) { int p = last, np = last = ++ tot; f[tot] = 1; node[np].len = node[p].len + 1; for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np; if(!p) node[np].fa = 1; else{ int q = node[p].ch[c]; if(node[q].len == node[p].len + 1) node[np].fa = q; else{ int nq = ++ tot; node[nq] = node[q], node[nq].len = node[p].len + 1; node[q].fa = node[np].fa = nq; for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq; } } } void add(int x, int y) { idx ++; e[idx] = y, ne[idx] = h[x], h[x] = idx; } void dfs(int x) { for(int i = h[x]; ~i; i = ne[i]) { dfs(e[i]); f[x] += f[e[i]]; } if(f[x] > 1) ans = max(ans, f[x] * node[x].len); } int main() { scanf("%s", str); for(int i = 0; str[i];i ++) extend(str[i] - 'a'); memset(h, -1, sizeof(h)); for(int i = 2; i <= tot; i ++) add(node[i].fa, i); dfs(1); printf("%lld\n", ans); return 0; }
|