先对母串建立后缀自动机。
然后建出link树。
然后,在link树上算出每个节点的子树大小,子树大小*len[i]就是当前节点所表示的字符串的长度乘出现次数。
坑:后缀自动机里存在虚拟节点,这些节点的sz是0.
处理方法就是只对cur记sz[cur]=1,对clone不管。
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+10;
int len[maxn],link[maxn],nxt[maxn][26];
int sz[maxn];
int tot=1,lst=1;
string s;
void sam_extend (char c) {
int cur=++tot;
len[cur]=len[lst]+1;
sz[cur]=1;
int p=lst;
while (p&&!nxt[p][c-'a']) {
nxt[p][c-'a']=cur;
p=link[p];
}
if (!p) {
link[cur]=1;
}
else {
int q=nxt[p][c-'a'];
if (len[p]+1==len[q]) {
link[cur]=q;
}
else {
int clone=++tot;
len[clone]=len[p]+1;
for (int i=0;i<26;i++) {
nxt[clone][i]=nxt[q][i];
}
link[clone]=link[q];
while (p&&nxt[p][c-'a']==q) {
nxt[p][c-'a']=clone;
p=link[p];
}
link[q]=link[cur]=clone;
}
}
lst=cur;
}
vector<int> g[maxn];
void dfs (int u) {
for (int v:g[u]) {
dfs(v);
sz[u]+=sz[v];
}
}
int main () {
cin>>s;
for (int i=0;i<s.size();i++) {
sam_extend(s[i]);
}
for (int i=2;i<=tot;i++) g[link[i]].push_back(i);
dfs(1);
long long ans=0;
for (int i=1;i<=tot;i++) {
if (sz[i]>1) {
ans=max(ans,1ll*len[i]*sz[i]);
}
}
printf("%lld\n",ans);
}