This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 600010
using namespace std;
struct PalTree{
struct Node{
int len, cnt, to[26], dub, slink;
Node() { len=0; cnt=0; dub=0; slink=0; for (int i=0; i<26; i++) to[i]=-1; }
Node(int a, int b, int c, int d)
{
len=a; cnt=b; dub=c; slink=d;
for (int i=0; i<26; i++) to[i]=-1;
}
};
vector<Node> pt;
int suff;
int s[MAXN];
int gde=0;
void addLetter(int c)
{
//cout<<gde<<" "<<suff<<endl;
s[gde]=c;
while (c!=s[gde-1-pt[suff].len])
suff=pt[suff].slink;
//cout<<suff<<endl;
int slnd=pt[suff].to[c];
if (slnd==-1)
{
slnd=pt.size();
pt[suff].to[c]=slnd;
pt.pb(Node(pt[suff].len+2, 0, 0, 0));
if (suff==1)
pt[slnd].slink=2;
else
{
int pom=pt[suff].slink;
while(c!=s[gde-1-pt[pom].len])
pom=pt[pom].slink;
pt[slnd].slink=pt[pom].to[c];
//assert(pom == 0);
assert(pt[pom].to[c] != -1);
//assert(pt[slnd].slink<pt.size());
}
pt[slnd].dub=pt[pt[slnd].slink].dub+1;
}
pt[slnd].cnt++;
suff=slnd;
gde++;
//cout<<slnd<<" "<<pt[slnd].slink<<endl;
}
void calc()
{
for (int i=pt.size()-1; i>2; i--){ pt[pt[i].slink].cnt+=pt[i].cnt; }
}
void init()
{
pt.clear();
pt.pb(Node(-1, -1, -1, -1));
pt.pb(Node(-1, 0, 0, 1));
pt.pb(Node(0, 0, 0, 1));
suff=2;
}
Node &operator[](int idx) {
return pt[idx];
}
};
PalTree pt;
ll ress=-1;
string st;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>st;
pt.init();
for (int i=0; i<st.size(); i++) pt.addLetter((int)(st[i]-'a'));
pt.calc();
for (int i=3; i<pt.pt.size(); i++)
{
ress=max(ress, ((ll)pt[i].cnt*pt[i].len));
}
cout<<ress;
}
Compilation message (stderr)
palindrome.cpp: In function 'int main()':
palindrome.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i=0; i<st.size(); i++) pt.addLetter((int)(st[i]-'a'));
| ~^~~~~~~~~~
palindrome.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PalTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i=3; i<pt.pt.size(); i++)
| ~^~~~~~~~~~~~~
# | 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... |