#include <bits/stdc++.h>
using namespace std;
struct node
{
int cnt, sz;
node *nxt[26], *suf;
node(int c, int s)
{
cnt=c;
sz=s;
for (int i=0; i<26; i++) nxt[i]=0;
}
};
typedef node* pnode;
pnode rt=new node(0, -1), srt=new node(0, 0), t=rt;
int n;
long long ans;
string s;
void dfs(pnode x)
{
for (int i=0; i<26; i++) if (x->nxt[i]) dfs(x->nxt[i]);
ans=max(ans, (long long)x->cnt*x->sz);
x->suf->cnt+=x->cnt;
//cout<<"exit "<<x->sz<<' '<<x->cnt<<'\n';
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
rt->suf=rt;
srt->suf=rt;
cin>>s;
n=s.size();
for (int i=0; i<n; i++)
{
//cout<<i<<'\n';
while (1)
{
//cout<<"debug "<<i<<" "<<t->sz<<'\n';
if (i-1-t->sz>=0&&s[i-1-t->sz]==s[i]) break;
t=t->suf;
}
//cout<<"here\n";
if (t->nxt[s[i]-'a'])
{
t=t->nxt[s[i]];
t->cnt++;
continue;
}
auto nw=new node(1, t->sz+2);
t->nxt[s[i]-'a']=nw;
if (nw->sz==1)
{
nw->suf=srt;
t=nw;
continue;
}
while (1)
{
t=t->suf;
if (i-1-t->sz>=0&&s[i-1-t->sz]==s[i])
{
nw->suf=t->nxt[s[i]-'a'];
break;
}
}
t=nw;
}
dfs(rt);
dfs(srt);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |