#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
//#define mod 998244353
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};//udlr
//const int dx[] = {-1, 1, 0, 0, 0}, dy[] = {0, 0, -1, 1, 0};
//const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}, dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') { f = -1; }
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = 10 * x + ch - '0';
ch = getchar();
}
return x * f;
}
#define IOS ios::sync_with_stdio(false);cin.tie(0), cout.tie(0)
#define endl "\n"
#define all(v) v.begin(),v.end()
//#define int long long
#define eu(v) v.erase(unique(all(v)), v.end())
#define lowbit(x) ((x)&(-(x)))
#define inf 0x3f3f3f3f
#define PII pair<int,int>
#define ll long long
#define PLL pair<ll,ll>
#define ull unsigned long long
#define lu (u<<1)
#define ru (u<<1|1)
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(b))
#define i128 __int128
#define eps 1e-6
#define debug(x) printf("%s = %lld\n",#x ,x)
#define y1 Feng_D
#define INF 0x3f3f3f3f3f3f3f3f
#define pi acos(-1.0)
#define sb setbuf(stdout,nullptr)
const int MAXN = 2e6 + 10;
char str[MAXN];
int tot = 1, last = 1;
struct Node
{
int len, fa;
int ch[26];
} node[MAXN];
ll f[MAXN], res;//f[i]表示这个类出现了多少次
int e[MAXN], ne[MAXN], h[MAXN], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void extend(int c)
{
//last表示没有加入c字符前的最长前缀所属节点的编号,tot是当前后缀自动机结点的总数
//设未加入c前的原串为旧串,加入c之后的为新串
//旧串的最大前缀就变成了新串的次大前缀
//用p记录新串次大前缀(原串的最大前缀)所属结点,np存放新的最大前缀所属的类
int p = last, np = last = ++tot;
f[tot] = 1;
//因为加了一个新的字符c,所以长度肯定要加1
node[np].len = node[p].len + 1;
//p=fa[p]的意思是从长到短遍历旧串的所有后缀
//node[p].ch[c] = np的意思是将旧串的所有后缀的后面加c形成新的字符串
//注意终止条件,如果长度再短,旧串的后缀加c形成的新字符串已经在旧串里面出现过了,所以就不需要连边了,避免重复,后缀自动机的里面表示的也是唯一的字符串子串
for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
//找到一个之后为什么不继续跳?因为如果再跳找到的新的节点q2,一定是第一次找到的q的祖先...我自己也不懂待定
//如果已经遍历完了旧串的所有后缀,并且他们加c都不是旧串的子串(最后一次循环是p=1,node[p].fa=0,此时后缀是空字符串)说明c是一个在旧串中没有出现过的字符
//续上...因此不可能存在除了结点1以外的fa,直接令fa[np]=1
if(!p) node[np].fa = 1;
else
{
//p在第一个有c的边的祖先停下了,q是p的c出边到达的结点
int q = node[p].ch[c];
//fa[x]类的最短字符串的长度一定小于x类的最短字符串,联想后缀,相当于可以说最短后缀代表了这一类
//”longest(p)+c“是新串的后缀,又因为len[q]=len[p]+1, “longest[q]=longest[p]+1", 所以longest(q)是新串的后缀
//续上...所以到达q类的所有串都是longest[q]的后缀,也即是到达q类的所有串都是新串的后缀,所以直接把np的父亲设置为q
//q是我们找到的第一个与np关系不同的且有后缀关系的节点,我们把fa[n]设为p
if(node[q].len == node[p].len + 1) node[np].fa = q;
else// 这里是len[q]!=len[p]+1,其实是len[q]>len[p]+1,因为p可以到q,所以len[q]>=len[p]+1,而这里又不相等,所以只能大于
{
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 DFS(int u)
{
for(int i = h[u]; ~i; i = ne[i])
{
DFS(e[i]);
f[u] += f[e[i]];
}
if(f[u] > 1)res = max(res, f[u] * node[u].len);
}
signed main()
{
scanf("%s", str);
for(int i = 0; str[i]; ++i)extend(str[i] - 'a');
mset(h, -1);
for(int i = 2; i <= tot; ++i)add(node[i].fa, i);
DFS(1);
printf("%lld", res);
return 0;
}
感谢注释