#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
const ll mod=1000000007,mxn=1000010;
string s;
int n;
ull p=313;
ull hap[mxn];
ull hal[mxn];
ull pot[mxn];
ll hap2[mxn];
ll hal2[mxn];
ll p2=2137;
ll pot2[mxn];
pair<ull,ll> gethp(int left,int right){
return mp(hap[right]-hap[left-1]*pot[right-left+1], ((hap2[right]-hap2[left-1]*pot2[right-left+1])%mod+mod)%mod );
}
pair<ull,ll> gethl(int left,int right){
return mp(hal[left]-hal[right+1]*pot[right-left+1] , ((hal2[left]-hal2[right+1]*pot2[right-left+1])%mod+mod)%mod ) ;
}
ll acc[mxn];
ll ilz[mxn];
ll wie[mxn][26];
ll ans;
void liczsro(int x){
int mn=1;
int mx=min(x,n-x+1);
////cout <<mx <<" ";
while(mn<mx){
int sr=(mn+mx+1)/2;
if(gethp(x-sr+1,x)==gethl(x,x+sr-1)){
mn=sr;
}
else{
mx=sr-1;
}
}
////cout <<mn <<" ";
acc[x-mn]+=1;
acc[x]-=2;
acc[x+mn]+=1;
ilz[x]-=mn;
int baz=mn;
ans+=baz;
if(baz==min(x,n-x+1)){
////cout <<"0\n";
return;
}
mx=min(x,n-x+1);
mn=baz+1;
while(mn<mx){
int sr=(mn+mx+1)/2;
if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+1,x+sr-1)){
mn=sr;
}
else{
mx=sr-1;
}
}
int dod=mn-baz;
////cout <<baz <<" "<<dod <<"\n";
char c1=s[x-baz-1]-'a';
char c2=s[x+baz-1]-'a';
wie[x-baz][c2]+=dod;
wie[x+baz][c1]+=dod;
////cout <<x <<" " <<baz <<" " <<c2+'a' <<"\n";
}
void liczd(int x){
int mn=0;
int mx=min(x,n-x);
while(mn<mx){
int sr=(mn+mx+1)/2;
if(gethp(x-sr+1,x)==gethl(x+1,x+sr)){
mn=sr;
}
else{
mx=sr-1;
}
}
////cout <<mn <<" ";
acc[x-mn]+=1;
acc[x]-=1;
acc[x+1]-=1;
acc[x+mn+1]+=1;
//ilz[x]-=mn;
int baz=mn;
ans+=baz;
if(baz==min(x,n-x)){
////cout <<"0 ";
return;
}
mx=min(x,n-x);
mn=baz+1;
////cout <<mx <<" ";
while(mn<mx){
int sr=(mn+mx+1)/2;
if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+2,x+sr)){
mn=sr;
}
else{
mx=sr-1;
}
}
ll dod=mn-baz;
////cout <<dod <<" ";
char c1=s[x-baz-1]-'a';
char c2=s[x+baz]-'a';
wie[x-baz][c2]+=dod;
wie[x+baz+1][c1]+=dod;
////cout <<x-baz <<" " <<'a'+c2 <<"\n";
}
void pro(){
ll pr=0;
ll val=0;
for(int i=0;i<=n;i++){
ilz[i]+=val;
pr+=acc[i];
val+=pr;
}
}
int main(){
cin >>s;
n=s.size();
pot[0]=1;
pot2[0]=1;
for(ull i=1;i<=mxn-10;i++){
pot[i]=pot[i-1]*p;
pot2[i]=pot2[i-1]*p2%mod;
}
for(int i=0;i<n;i++){
hap[i+1]=hap[i]*p+s[i];
hap2[i+1]=(hap2[i]*p2+s[i])%mod;
}
for(int i=n;i>0;i--){
hal[i]=hal[i+1]*p+s[i-1];
hal2[i]=(hal2[i+1]*p2+s[i-1])%mod;
}
/*while(1){
int a,b;
cin >>a >>b;
//cout <<gethp(a,b) <<"\n";
//cout <<gethl(a,b) <<"\n";
}*/
for(int i=1;i<=n;i++){
liczsro(i);
}
////cout <<"\n";
for(int i=1;i<n;i++){
liczd(i);
}
////cout <<"\n";
pro();
////cout <<"\n";
/*for(int i=0;i<=n;i++){
//cout <<acc[i] <<" ";
}
//cout <<"\n";
*/
/*for(int i=0;i<=n;i++){
//cout <<ilz[i] <<" ";
}*/
//cout <<ans<<"\n";
ll wyn=ans;
for(int i=1;i<=n;i++){
//cout <<ilz[i] <<" ";
for(int j=0;j<26;j++){
wyn=max(wyn,ans+wie[i][j]-ilz[i]);
}
}
//cout <<"\n";
for(int i=1;i<=n;i++){
ll x=0;
for(int j=0;j<26;j++){
x=max(x,wie[i][j]);
}
//cout <<x<<" ";
}
//cout <<"\n";
cout <<wyn;
}
Compilation message
palinilap.cpp: In function 'void liczsro(int)':
palinilap.cpp:72:15: warning: array subscript has type 'char' [-Wchar-subscripts]
wie[x-baz][c2]+=dod;
^
palinilap.cpp:73:15: warning: array subscript has type 'char' [-Wchar-subscripts]
wie[x+baz][c1]+=dod;
^
palinilap.cpp: In function 'void liczd(int)':
palinilap.cpp:116:15: warning: array subscript has type 'char' [-Wchar-subscripts]
wie[x-baz][c2]+=dod;
^
palinilap.cpp:117:17: warning: array subscript has type 'char' [-Wchar-subscripts]
wie[x+baz+1][c1]+=dod;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16128 KB |
Output is correct |
| 3 |
Correct |
20 ms |
16128 KB |
Output is correct |
| 4 |
Correct |
19 ms |
16128 KB |
Output is correct |
| 5 |
Correct |
18 ms |
16128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
17280 KB |
Output is correct |
| 2 |
Correct |
26 ms |
17400 KB |
Output is correct |
| 3 |
Correct |
24 ms |
17280 KB |
Output is correct |
| 4 |
Correct |
23 ms |
16904 KB |
Output is correct |
| 5 |
Correct |
25 ms |
17152 KB |
Output is correct |
| 6 |
Correct |
24 ms |
17404 KB |
Output is correct |
| 7 |
Correct |
26 ms |
17280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
41448 KB |
Output is correct |
| 2 |
Correct |
140 ms |
41384 KB |
Output is correct |
| 3 |
Correct |
119 ms |
41336 KB |
Output is correct |
| 4 |
Correct |
137 ms |
41336 KB |
Output is correct |
| 5 |
Correct |
120 ms |
41380 KB |
Output is correct |
| 6 |
Correct |
122 ms |
41464 KB |
Output is correct |
| 7 |
Correct |
140 ms |
41480 KB |
Output is correct |
| 8 |
Correct |
77 ms |
21112 KB |
Output is correct |
| 9 |
Correct |
120 ms |
41348 KB |
Output is correct |
| 10 |
Correct |
124 ms |
41436 KB |
Output is correct |
| 11 |
Correct |
130 ms |
41324 KB |
Output is correct |
| 12 |
Correct |
143 ms |
41344 KB |
Output is correct |
| 13 |
Correct |
134 ms |
41508 KB |
Output is correct |
| 14 |
Correct |
151 ms |
41488 KB |
Output is correct |
| 15 |
Correct |
163 ms |
41316 KB |
Output is correct |
| 16 |
Correct |
148 ms |
41464 KB |
Output is correct |
| 17 |
Correct |
120 ms |
41336 KB |
Output is correct |
| 18 |
Correct |
143 ms |
41340 KB |
Output is correct |
| 19 |
Correct |
120 ms |
41384 KB |
Output is correct |
