描述
题解
用 kmp 处理一下获取一个 next 数组即可,然后递推一遍,O(n),简单快捷,完美!
代码
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 10;
char str[MAXN];
int len;
int nt[MAXN];
int res[MAXN];
void getNext()
{
nt[0] = -1;
int i = 0, j = -1;
while (i <= len)
{
if (j == -1 || str[i] == str[j])
{
nt[++i] = ++j;
}
else
{
j = nt[j];
}
}
}
int main()
{
scanf("%s", str);
len = (int)strlen(str);
getNext();
for (int i = len; i >= 1; i--)
{
res[i]++;
res[nt[i]] += res[i];
}
long long ans = 0;
for (long long i = 1; i <= len; i++)
{
ans = max(i * res[i], ans);
}
printf("%lld\n", ans);
return 0;
}