代码拉取完成,页面将自动刷新
#include<bits/stdc++.h>
using namespace std;
const int N = 2000010;
int tot = 1, last = 1;
struct Node
{
int len, fa;
int s[26];
}node[N];
char str[N];
long long f[N];
long long ans;
int h[N], e[N], ne[N], idx;
void extend(int c)
{
int p = last, np = last = ++tot;
f[tot] = 1;
node[np].len = node[p].len + 1;
for(; (p) && (!node[p].s[c]); p = node[p].fa)node[p].s[c] = np;
if(!p)
{
node[np].fa = 1;
}
else
{
int q = node[p].s[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].s[c] == q); p = node[p].fa)node[p].s[c] = nq;
}
}
return;
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
return;
}
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)ans = max(ans, f[u] * node[u].len);
return;
}
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;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。