题目链接
题解
对于单串，考虑多串的fail树，发现next数组的关系形成树形结构
建出next树，对于每一个前缀，他出现的次数就是他子树的大小
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
const int maxn = 100007;
struct node {
int v,next;
} edge[maxn << 1];
int num = 0,head[maxn];
inline void add_edge(int u,int v) {
edge[++ num].v = v; edge[num].next = head[u];head[u] = num;
}
long long siz[maxn];
char s[maxn];
int next[maxn];
int len = 0;
void getnext() {
next[0] = -1;
for(int j = 0,i = 2;i <= len;++ i) {
for(;s[i] != s[j + 1] && j > 0;j = next[j]);
if(s[i] == s[j + 1]) { next[i] = j + 1,++ j; add_edge(j,i); }
}
}
long long ans = 0;
void dfs(int x) {
siz[x] = 1;
for(int i = head[x];i;i = edge[i].next) {
dfs(edge[i].v);
siz[x] += siz[edge[i].v];
}
ans = std::max(ans, (long long) x * siz[x]);
}
int main() {
scanf("%s",s + 1);
len = strlen(s + 1);
getnext();
for(int i = 1;i <= len;++ i) if(!next[i]) dfs(i);
printf("%lld\n",ans);
return 0;
}