/*
abacaba
*/
#include<bits/stdc++.h>
#define int long long
#define hash hash2
using namespace std;
const int N=3e5+14;
const int mod=1e9+9;
const int base=211;
const int mod1=1610612741;
int hash[N],rev_hash[N],mul[N],max1=1,sum[N],mul1[N],hash1[N],rev_hash1[N];
map<pair<int,int>,int> cnt;
pair<int,int> gethash(int l,int r){
return {((hash[r]-hash[l-1]*mul[r-l+1])%mod+mod)%mod,((hash1[r]-hash1[l-1]*mul1[r-l+1])%mod1+mod1)%mod1};
}
pair<int,int> gethash_rev(int l,int r){
return {((rev_hash[l]-rev_hash[r+1]*mul[r-l+1])%mod+mod)%mod,((rev_hash1[l]-rev_hash1[r+1]*mul1[r-l+1])%mod1+mod1)%mod1};
}
struct node{
int nxt[26],len,suf;
};
node Eer[N];
int sz=0,lst;
string s;
void add(int idx){
// cout<<idx<<" BEGIN"<<endl;
int cha=(s[idx]-'a');
while(idx-Eer[lst].len-1<0||s[idx]!=s[idx-Eer[lst].len-1]){
lst=Eer[lst].suf;
}
if(!Eer[lst].nxt[cha]){
sz++;
Eer[lst].nxt[cha]=sz;
Eer[sz].len=Eer[lst].len+2;
if(Eer[sz].len!=1){
int sf=Eer[lst].suf;
while(idx-Eer[sf].len-1<0||s[idx]!=s[idx-Eer[sf].len-1]){
sf=Eer[sf].suf;
}
Eer[sz].suf=Eer[sf].nxt[cha];
}
else{
Eer[sz].suf=2;
}
}
lst=Eer[lst].nxt[cha];
return;
}
void build(string s1){
sz=2;
Eer[1].len=-1;
Eer[1].suf=0;
Eer[2].len=0;
Eer[2].suf=1;
lst=2;
s=s1;
for(int i=0;i<s.size();i++){
add(i);
}
}
void dfs(int x,pair<int,int> val){
sum[x]=cnt[val];
for(int i=0;i<26;i++){
if(Eer[x].nxt[i]){
if(x==1){
dfs(Eer[x].nxt[i],{i+1,i+1});
}
else{
dfs(Eer[x].nxt[i],{(i+1+val.first*base+(i+1)*mul[Eer[x].len+1])%mod,(i+1 + val.second*base + (i+1)*mul1[Eer[x].len+1])%mod1});
}
sum[x]+=sum[Eer[x].nxt[i]];
}
}
max1=max(max1,Eer[x].len * sum[x]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s1;
cin>>s1;
build(s1);
int n=s1.size(),i,j,k,l;
s1=" "+s1;
mul[0]=1;
mul1[0]=1;
for(i=1;i<=n;i++){
hash[i]=(hash[i-1]*base+(s1[i]-'a'+1))%mod;
mul[i]=(mul[i-1]*base)%mod;
hash1[i]=(hash1[i-1]*base+(s1[i]-'a'+1))%mod1;
mul1[i]=(mul1[i-1]*base)%mod1;
}
for(i=n;i>0;i--){
rev_hash[i]=(rev_hash[i+1]*base+(s1[i]-'a'+1))%mod;
rev_hash1[i]=(rev_hash1[i+1]*base+(s1[i]-'a'+1))%mod1;
}
for(i=1;i<=n;i++){
k=0;
l=min(i-1,n-i);
while(k<l){
j=(k+l+1)>>1;
if(gethash(i-j,i+j)==gethash_rev(i-j,i+j)){
k=j;
}
else{
l=j-1;
}
}
cnt[gethash(i-k,i+k)]++;
if(i<=n&&s1[i]==s1[i+1]){
k=0;
l=min(i-1,n-i-1);
while(k<l){
j=(k+l+1)>>1;
if(gethash(i-j,i+1+j)==gethash_rev(i-j,i+1+j)){
k=j;
}
else{
l=j-1;
}
}
cnt[gethash(i-k,i+1+k)]++;
}
}
dfs(1,{0,0});
dfs(2,{0,0});
cout<<max1;
}
Compilation message
palindrome.cpp: In function 'void build(std::__cxx11::string)':
palindrome.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.size();i++){
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
424 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
380 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
380 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
380 KB |
Output is correct |
19 |
Correct |
2 ms |
420 KB |
Output is correct |
20 |
Correct |
2 ms |
504 KB |
Output is correct |
21 |
Correct |
2 ms |
580 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
504 KB |
Output is correct |
28 |
Correct |
2 ms |
504 KB |
Output is correct |
29 |
Correct |
2 ms |
504 KB |
Output is correct |
30 |
Correct |
2 ms |
380 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
760 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
760 KB |
Output is correct |
7 |
Correct |
2 ms |
760 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
504 KB |
Output is correct |
12 |
Correct |
3 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
4088 KB |
Output is correct |
2 |
Correct |
13 ms |
3940 KB |
Output is correct |
3 |
Correct |
19 ms |
4088 KB |
Output is correct |
4 |
Correct |
17 ms |
4088 KB |
Output is correct |
5 |
Correct |
11 ms |
4088 KB |
Output is correct |
6 |
Correct |
12 ms |
3980 KB |
Output is correct |
7 |
Correct |
14 ms |
3960 KB |
Output is correct |
8 |
Correct |
5 ms |
1016 KB |
Output is correct |
9 |
Correct |
5 ms |
1016 KB |
Output is correct |
10 |
Correct |
9 ms |
2940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
37368 KB |
Output is correct |
2 |
Correct |
168 ms |
35960 KB |
Output is correct |
3 |
Correct |
258 ms |
37512 KB |
Output is correct |
4 |
Correct |
230 ms |
36344 KB |
Output is correct |
5 |
Correct |
154 ms |
36472 KB |
Output is correct |
6 |
Correct |
113 ms |
27512 KB |
Output is correct |
7 |
Correct |
171 ms |
30432 KB |
Output is correct |
8 |
Correct |
48 ms |
5768 KB |
Output is correct |
9 |
Correct |
84 ms |
12980 KB |
Output is correct |
10 |
Correct |
124 ms |
32056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
716 ms |
111252 KB |
Output is correct |
2 |
Correct |
756 ms |
104948 KB |
Output is correct |
3 |
Execution timed out |
1034 ms |
111576 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |