1 Star 0 Fork 0

南陽劉子驥 / OI Codes

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
p3804.cpp 1.19 KB
一键复制 编辑 原始数据 按行查看 历史
南陽劉子驥 提交于 2022-06-15 14:11 . 20220615
#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;
}
1
https://gitee.com/kaiserwilheim/OIcodes.git
git@gitee.com:kaiserwilheim/OIcodes.git
kaiserwilheim
OIcodes
OI Codes
master

搜索帮助