#include <bits/stdc++.h>
using namespace std;
const int MX=300005;
struct node{
int len,link,cnt;
map <char,int> to;
};
node pt[MX];
int size,last;
char s[MX];
vector <int> idx[MX];
void init_node(int n)
{
pt[n].len=0;
pt[n].cnt=0;
pt[n].link=-1;
pt[n].to.clear();
}
void init_pt()
{
init_node(0);
init_node(1);
pt[0].len=pt[0].link=-1;
pt[1].link=0;
size=2,last=1;
}
int find(int n,char s[],int i)
{
while(n){
int j=i-pt[n].len-1;
if(j>=0 && s[i]==s[j]) return n;
n=pt[n].link;
}
return n;
}
void extend(char s[],int i)
{
int n=find(last,s,i);
if(pt[n].to.count(s[i])==0){
int m=size++;
init_node(m);
pt[n].to[s[i]]=m;
pt[m].len=pt[n].len+2;
if(pt[m].len==1) pt[m].link=1;
else{
int v=find(pt[n].link,s,i);
pt[m].link=pt[v].to[s[i]];
}
last=m;
}
else last=pt[n].to[s[i]];
}
int main()
{
scanf("%s",s);
int n=strlen(s);
init_pt();
for(int i=0;i<n;i++){
extend(s,i);
pt[last].cnt++;
idx[pt[last].len].push_back(last);
}
for(int i=n;i>0;i--){
int l=idx[i].size();
for(int j=0;j<l;j++){
int v=idx[i][j];
int u=pt[v].link;
if(u>1) pt[u].cnt+=pt[v].cnt;
}
}
int ans=0;
for(int i=2;i<size;i++){
ans=max(ans,pt[i].cnt*pt[i].len);
}
printf("%d\n",ans);
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);
~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
26104 KB |
Output is correct |
2 |
Correct |
25 ms |
26104 KB |
Output is correct |
3 |
Correct |
25 ms |
26104 KB |
Output is correct |
4 |
Correct |
23 ms |
26104 KB |
Output is correct |
5 |
Correct |
26 ms |
26176 KB |
Output is correct |
6 |
Correct |
25 ms |
26104 KB |
Output is correct |
7 |
Correct |
25 ms |
26104 KB |
Output is correct |
8 |
Correct |
25 ms |
26104 KB |
Output is correct |
9 |
Correct |
31 ms |
26104 KB |
Output is correct |
10 |
Correct |
26 ms |
26104 KB |
Output is correct |
11 |
Incorrect |
25 ms |
26104 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
26232 KB |
Output is correct |
2 |
Correct |
25 ms |
26232 KB |
Output is correct |
3 |
Correct |
25 ms |
26272 KB |
Output is correct |
4 |
Correct |
25 ms |
26232 KB |
Output is correct |
5 |
Correct |
26 ms |
26232 KB |
Output is correct |
6 |
Correct |
25 ms |
26236 KB |
Output is correct |
7 |
Correct |
25 ms |
26236 KB |
Output is correct |
8 |
Correct |
26 ms |
26232 KB |
Output is correct |
9 |
Incorrect |
26 ms |
26160 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
26716 KB |
Output is correct |
2 |
Correct |
28 ms |
26744 KB |
Output is correct |
3 |
Correct |
28 ms |
26988 KB |
Output is correct |
4 |
Correct |
28 ms |
26872 KB |
Output is correct |
5 |
Correct |
27 ms |
26748 KB |
Output is correct |
6 |
Correct |
27 ms |
26744 KB |
Output is correct |
7 |
Correct |
27 ms |
26744 KB |
Output is correct |
8 |
Incorrect |
26 ms |
26224 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
32564 KB |
Output is correct |
2 |
Correct |
44 ms |
31964 KB |
Output is correct |
3 |
Incorrect |
48 ms |
34224 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
92 ms |
45212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |