#include<bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define pb push_back
#define siz 100009
#define inf 1e9+8
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define repo(i,m,n) for(int i=m;i<=n;i++)
#define ll long long
#define pii pair<int,int >
#define sc(n) scanf("%d",&n)
#define sc2(m,n) scanf("%d%d",&m,&n);
#define MOD 4294967296
#define fileout freopen("output.txt","w",stdout)
#define filein freopen("input.txt","r",stdin)
#define mem(x,i) memset(x,i,sizeof x)
#define PI acos(-1.0)
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define Case(t) for(int ks=1;ks<=t;ks++)
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
const int N=1e5+10;
int tree[N][26],idx;
ll len[N];int link[N];
int ans[N],occ[N];
int t;
string str;
void extend(int p)
{
while(str[p-len[t]-1]!=str[p])
t=link[t];
int x=link[t],c=str[p]-'a';
while(str[p-len[x]-1]!=str[p])
x=link[x];
if(!tree[t][c])
{
tree[t][c]=++idx;
len[idx]=len[t]+2;
link[idx]=(len[idx]==1?2:tree[x][c]);
ans[idx]=1+ans[link[idx]];
}
t=tree[t][c];
++occ[t];
}
int main()
{
{
mem(tree,0);
len[1]=-1;
len[2]=0;
link[1]=link[2]=1;
idx=t=2;
cin>>str;
str=' '+str;
int n=str.size();
ll val=0;
for(int i=1; i<str.size(); i++)
{
extend(i);
//val+=ans[t];
}
for(int i=idx;i>2;i--) occ[link[i]]+=occ[i];
for(int i=3;i<=idx;i++)val=max(val,occ[i]*len[i]);
printf("%d\n",val);
}
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<str.size(); i++)
~^~~~~~~~~~~
palindrome.cpp:74:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d\n",val);
^
palindrome.cpp:65:13: warning: unused variable 'n' [-Wunused-variable]
int n=str.size();
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10488 KB |
Output is correct |
2 |
Correct |
12 ms |
10492 KB |
Output is correct |
3 |
Correct |
10 ms |
10488 KB |
Output is correct |
4 |
Correct |
12 ms |
10488 KB |
Output is correct |
5 |
Correct |
10 ms |
10488 KB |
Output is correct |
6 |
Correct |
12 ms |
10488 KB |
Output is correct |
7 |
Correct |
11 ms |
10488 KB |
Output is correct |
8 |
Correct |
10 ms |
10488 KB |
Output is correct |
9 |
Correct |
10 ms |
10488 KB |
Output is correct |
10 |
Correct |
12 ms |
10488 KB |
Output is correct |
11 |
Correct |
10 ms |
10488 KB |
Output is correct |
12 |
Correct |
10 ms |
10488 KB |
Output is correct |
13 |
Correct |
10 ms |
10488 KB |
Output is correct |
14 |
Correct |
10 ms |
10488 KB |
Output is correct |
15 |
Correct |
10 ms |
10488 KB |
Output is correct |
16 |
Correct |
12 ms |
10616 KB |
Output is correct |
17 |
Correct |
12 ms |
10488 KB |
Output is correct |
18 |
Correct |
10 ms |
10488 KB |
Output is correct |
19 |
Correct |
10 ms |
10488 KB |
Output is correct |
20 |
Correct |
10 ms |
10488 KB |
Output is correct |
21 |
Correct |
12 ms |
10488 KB |
Output is correct |
22 |
Correct |
12 ms |
10488 KB |
Output is correct |
23 |
Correct |
12 ms |
10544 KB |
Output is correct |
24 |
Correct |
12 ms |
10516 KB |
Output is correct |
25 |
Correct |
13 ms |
10492 KB |
Output is correct |
26 |
Correct |
12 ms |
10492 KB |
Output is correct |
27 |
Correct |
13 ms |
10488 KB |
Output is correct |
28 |
Correct |
12 ms |
10488 KB |
Output is correct |
29 |
Correct |
12 ms |
10492 KB |
Output is correct |
30 |
Correct |
12 ms |
10488 KB |
Output is correct |
31 |
Correct |
12 ms |
10488 KB |
Output is correct |
32 |
Correct |
12 ms |
10488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10460 KB |
Output is correct |
2 |
Correct |
10 ms |
10488 KB |
Output is correct |
3 |
Correct |
37 ms |
10488 KB |
Output is correct |
4 |
Correct |
12 ms |
10488 KB |
Output is correct |
5 |
Correct |
10 ms |
10488 KB |
Output is correct |
6 |
Correct |
10 ms |
10488 KB |
Output is correct |
7 |
Correct |
13 ms |
10464 KB |
Output is correct |
8 |
Correct |
10 ms |
10512 KB |
Output is correct |
9 |
Correct |
11 ms |
10488 KB |
Output is correct |
10 |
Correct |
11 ms |
10488 KB |
Output is correct |
11 |
Correct |
10 ms |
10488 KB |
Output is correct |
12 |
Correct |
10 ms |
10488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10744 KB |
Output is correct |
2 |
Correct |
11 ms |
10744 KB |
Output is correct |
3 |
Correct |
11 ms |
10744 KB |
Output is correct |
4 |
Correct |
11 ms |
10748 KB |
Output is correct |
5 |
Correct |
11 ms |
10744 KB |
Output is correct |
6 |
Correct |
11 ms |
10744 KB |
Output is correct |
7 |
Correct |
14 ms |
10744 KB |
Output is correct |
8 |
Correct |
11 ms |
10488 KB |
Output is correct |
9 |
Correct |
13 ms |
10616 KB |
Output is correct |
10 |
Correct |
11 ms |
10616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
12632 KB |
Output is correct |
2 |
Correct |
23 ms |
12660 KB |
Output is correct |
3 |
Incorrect |
22 ms |
12660 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1059 ms |
12904 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |