#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];
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);
int u=last;
while(u>1){
pt[u].cnt++;
u=pt[u].link;
}
}
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:54: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 |
19 ms |
19064 KB |
Output is correct |
2 |
Correct |
19 ms |
19192 KB |
Output is correct |
3 |
Correct |
19 ms |
19064 KB |
Output is correct |
4 |
Correct |
19 ms |
19108 KB |
Output is correct |
5 |
Correct |
19 ms |
19064 KB |
Output is correct |
6 |
Correct |
19 ms |
19064 KB |
Output is correct |
7 |
Correct |
19 ms |
19064 KB |
Output is correct |
8 |
Correct |
19 ms |
19064 KB |
Output is correct |
9 |
Correct |
19 ms |
19064 KB |
Output is correct |
10 |
Correct |
19 ms |
19064 KB |
Output is correct |
11 |
Correct |
19 ms |
19064 KB |
Output is correct |
12 |
Correct |
19 ms |
19068 KB |
Output is correct |
13 |
Correct |
19 ms |
19188 KB |
Output is correct |
14 |
Correct |
43 ms |
19064 KB |
Output is correct |
15 |
Correct |
19 ms |
19064 KB |
Output is correct |
16 |
Correct |
19 ms |
19064 KB |
Output is correct |
17 |
Correct |
19 ms |
19064 KB |
Output is correct |
18 |
Correct |
20 ms |
19064 KB |
Output is correct |
19 |
Correct |
19 ms |
19064 KB |
Output is correct |
20 |
Correct |
19 ms |
19064 KB |
Output is correct |
21 |
Correct |
19 ms |
19064 KB |
Output is correct |
22 |
Correct |
19 ms |
19064 KB |
Output is correct |
23 |
Correct |
19 ms |
19064 KB |
Output is correct |
24 |
Correct |
19 ms |
19192 KB |
Output is correct |
25 |
Correct |
19 ms |
19120 KB |
Output is correct |
26 |
Correct |
18 ms |
19064 KB |
Output is correct |
27 |
Correct |
19 ms |
19064 KB |
Output is correct |
28 |
Correct |
18 ms |
19192 KB |
Output is correct |
29 |
Correct |
18 ms |
19064 KB |
Output is correct |
30 |
Correct |
19 ms |
19064 KB |
Output is correct |
31 |
Correct |
18 ms |
19064 KB |
Output is correct |
32 |
Correct |
19 ms |
19192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
19192 KB |
Output is correct |
2 |
Correct |
19 ms |
19192 KB |
Output is correct |
3 |
Correct |
21 ms |
19196 KB |
Output is correct |
4 |
Correct |
19 ms |
19192 KB |
Output is correct |
5 |
Correct |
22 ms |
19192 KB |
Output is correct |
6 |
Correct |
21 ms |
19192 KB |
Output is correct |
7 |
Correct |
19 ms |
19192 KB |
Output is correct |
8 |
Correct |
20 ms |
19192 KB |
Output is correct |
9 |
Correct |
19 ms |
19064 KB |
Output is correct |
10 |
Correct |
20 ms |
19128 KB |
Output is correct |
11 |
Correct |
19 ms |
19064 KB |
Output is correct |
12 |
Correct |
19 ms |
19192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
218 ms |
19576 KB |
Output is correct |
2 |
Correct |
127 ms |
19624 KB |
Output is correct |
3 |
Correct |
357 ms |
19572 KB |
Output is correct |
4 |
Correct |
268 ms |
19796 KB |
Output is correct |
5 |
Correct |
21 ms |
19576 KB |
Output is correct |
6 |
Correct |
28 ms |
19704 KB |
Output is correct |
7 |
Correct |
53 ms |
19620 KB |
Output is correct |
8 |
Correct |
20 ms |
19064 KB |
Output is correct |
9 |
Correct |
20 ms |
19192 KB |
Output is correct |
10 |
Correct |
20 ms |
19448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1069 ms |
20592 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1078 ms |
20864 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |