你没有看错，菜鸡退役前刚学后缀自动机
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
#define M 2000010
#define mmp make_pair
using namespace std;
int read()
{
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
int fa[M], ch[M][26], len[M], sz[M], t[M], a[M], lst = 1, cnt = 1;
char s[M];
void insert(int c)
{
int f = lst, p = ++cnt;
lst = p;
len[p] = len[f] + 1;
sz[p] = 1;
while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
if(!f)
{
fa[p] = 1;
return;
//情况1
}
int q = ch[f][c], nq = ++cnt;
if(len[f] + 1 == len[q])
{
fa[p] = q;
cnt--;
//情况二 max = min - 1
return;
}
// 情况3 有中转
len[nq] = len[f] + 1;
fa[nq] = fa[q];
fa[q] = fa[p] = nq;
memcpy(ch[nq], ch[q], sizeof(ch[nq]));
while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
}
int main()
{
scanf("%s", s + 1);
int le = strlen(s + 1);
for(int i = 1; i <= le; i++) insert(s[i] - 'a');
for(int i = 1; i <= cnt; i++) t[len[i]]++;
for(int i = 1; i <= cnt; i++) t[i] += t[i - 1];
for(int i = 1; i <= cnt; i++) a[t[len[i]]--] = i;
ll ans = 0;
for(int i = cnt; i >= 1; i--)
{
int now = a[i];
sz[fa[now]] += sz[now];
if(sz[now] > 1) ans = max(ans, 1ll * sz[now] * len[now]);
}
cout << ans << "\n";
return 0;
}
转载于:https://www.cnblogs.com/luoyibujue/p/10596504.html
