#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const ll P1=313LL;
const ll P2=220721LL;
const ll M=1000LL*1000LL*1000LL+21LL;
const ll M2=1000000007LL;
char Wczytaj[N];
ll Potegi1[N];
ll Potegi2[N];
ll Hasz1[N][2];
ll Hasz2[N][2];
ll Plus[N][33];
ll Minus[N];
pair<ll, ll>CA[N];
ll wynik=0LL;
void LiczPotegi(){
Potegi1[0]=Potegi2[0]=1LL;
for(int i=1; i<N; i++){
Potegi1[i]=(Potegi1[i-1]*P1)%M;
Potegi2[i]=(Potegi2[i-1]*P2)%M2;
}
}
void WczytajDane(int &n){
string slowo;
getline(cin, slowo);
n=(int)slowo.size();
for(int i=1; i<=n; i++) Wczytaj[i]=slowo[i-1];
}
void LiczHasze(int n){
for(int i=1; i<=n; i++){
Hasz1[i][0]=( Hasz1[i-1][0]+Potegi1[i]*(ll)Wczytaj[i] )%M;
Hasz2[i][0]=( Hasz2[i-1][0]+Potegi2[i]*(ll)Wczytaj[i] )%M2;
}
for(int i=n; i>=1; i--){
Hasz1[i][1]=( Hasz1[i+1][1]+Potegi1[n-i+1]*(ll)Wczytaj[i] )%M;
Hasz2[i][1]=( Hasz2[i+1][1]+Potegi2[n-i+1]*(ll)Wczytaj[i] )%M2;
}
}
int CzyRowne(int p1, int k1, int p2, int k2, int n){
int h1, h2, h3, h4;
h1=(Hasz1[k1][0]-Hasz1[p1-1][0]+M)%M; h2=(Hasz2[k1][0]-Hasz2[p1-1][0]+M2)%M2;
h3=(Hasz1[p2][1]-Hasz1[k2+1][1]+M)%M; h4=(Hasz2[p2][1]-Hasz2[k2+1][1]+M2)%M2;
if( p1>n-k2+1 ){
h3=(h3*Potegi1[ p1-n+k2-1 ])%M;
h4=(h4*Potegi2[ p1-n+k2-1 ])%M2;
}
else{
h1=(h1*Potegi1[ n-k2+1-p1 ])%M;
h2=(h2*Potegi2[ n-k2+1-p1 ])%M2;
}
if(h1==h3 && h2==h4) return 1;
return 0;
}
int JakDaleko(int pl, int pp, int n){
int p, k, s;
if(pl<1 || pp>n || Wczytaj[pl]!=Wczytaj[pp]) return 0;
p=1; k=min(pl, n-pp+1);
while(p<k){
s=(p+k+1)/2;
if( CzyRowne(pl-s+1, pl, pp, pp+s-1, n) ) p=s;
else k=s-1;
}
return p;
}
void Dodaj(int p, int k, ll pw, ll roz){
CA[p].first+=pw; CA[p].second+=roz;
CA[k+1].first-=(pw+(ll)(k-p+1)*roz); CA[k+1].second-=roz;
}
void LiczPalindromyNieparzyste(int n){
int d, d2;
Minus[1]++; Minus[n]++;
wynik+=2LL;
for(int i=2; i<n; i++){
d=JakDaleko(i-1, i+1, n)+1;
wynik+=(ll)d;
Minus[i]-=(ll)(d-1);
Dodaj(i-d+1, i, 1LL, 1LL);
Dodaj(i+1, i+d-1, (ll)(d-1), -1LL);
d2=JakDaleko(i-d-1, i+d+1, n)+1;
if( i-d<1 || i+d>n ) continue;
Plus[i-d][ (int)Wczytaj[i+d]-96 ]+=(ll)d2;
Plus[i+d][ (int)Wczytaj[i-d]-96 ]+=(ll)d2;
}
}
void LiczPalindromyParzyste(int n){
int d, d2;
for(int i=1; i<n; i++){
if( Wczytaj[i]==Wczytaj[i+1] ){
d=JakDaleko(i, i+1, n);
Dodaj(i-d+1, i, 1LL, 1LL);
Dodaj(i+1, i+1+d-1, (ll)d, -1LL);
wynik+=(ll)d;
d2=JakDaleko(i-d-1, i+1+d+1, n)+1;
if( i-d<1 || i+d+1>n ) continue;
Plus[i-d][ (int)Wczytaj[i+d+1]-96 ]+=(ll)d2;
Plus[i+d+1][ (int)Wczytaj[i-d]-96 ]+=(ll)d2;
continue;
}
d=JakDaleko(i-1, i+2, n)+1;
Plus[i][ (int)Wczytaj[i+1]-96 ]+=(ll)d;
Plus[i+1][ (int)Wczytaj[i]-96 ]+=(ll)d;
}
}
void WyliczCA(int n){
pair<ll, ll> aktu=make_pair(0LL, 0LL);
for(int i=1; i<=n; i++){
aktu.first+=CA[i].first; aktu.second+=CA[i].second;
Minus[i]+=aktu.first;
aktu.first+=aktu.second;
}
}
ll Zamiana(int n){
ll wynik1=0LL;
for(int i=1; i<=n; i++){
for(int j=1; j<=30; j++){
if( j==(int)Wczytaj[i]-96 ) continue;
wynik1=max(wynik1, wynik-Minus[i]+Plus[i][j]+1LL);
}
}
return wynik1;
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
WczytajDane(n);
LiczPotegi();
LiczHasze(n);
LiczPalindromyNieparzyste(n);
LiczPalindromyParzyste(n);
WyliczCA(n);
cout<< max( Zamiana(n), wynik )-1LL << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3584 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
3584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
33492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
