#include<bits/stdc++.h>
#define N 100100
using namespace std;
#define X (1<<j)
long long ans,nc,cont[N][26],bad[2][N],n,hl[N],hr[N],pw[N]{1},A=31,B=1e9+7;
int Hl(int l, int r) {return(hl[r]-hl[l]*pw[r-l]%B+B)%B;}
int Hr(int l, int r) {return(hr[l]-hr[r]*pw[r-l]%B+B)%B;}
int main() {
for(int i=1;i<N;i++) pw[i]=pw[i-1]*A%B;
string str;
char c=getchar();
while(c>'A')str+=c,c=getchar();
n=str.size();
for(int i=1;i<=n;i++)
hl[i]=hr[i]=str[i-1]-'a'+1;
for(int i=1;i<n;i++)
hl[i+1]+=hl[i]*A,
hr[n-i]+=hr[n-i+1]*A;
for(int i=1;i<=n;i++){
int p1=i,p2=i,p3,p4;
for(int j = 20; j--;)
if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
p1-=X,p2+=X;
bad[0][i+1]++,bad[0][p2]+=i-p2,bad[0][p2+1]+=p2-i-1;
nc+=i-p1;
bad[1][i-1]++,bad[1][p1]+=p1-i;if(p1)bad[1][p1-1]+=i-p1-1;
p3=p1--,p4=p2++;
for(int j = 20; j--;)
if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
p1-=X,p2+=X;
if(p3&&p4<=n)cont[p3][str[p4-1]-'a']+=p3-p1,
cont[p4][str[p3-1]-'a']+=p3-p1;
}
for(int i=1;i<n;i++){
int p1=i,p2=i+1,p3,p4;
for(int j = 20; j--;)
if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
p1-=X,p2+=X;
bad[0][i+1]++,bad[0][p2]+=i-p2,bad[0][p2+1]+=p2-i-1;
nc+=i-p1;
bad[1][i]++;bad[1][p1]+=p1-i-1;if(p1)bad[1][p1-1]+=i-p1;
p3=p1--,p4=p2++;
for(int j = 20; j--;)
if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
p1-=X,p2+=X;
if(p3&&p4<=n)cont[p3][str[p4-1]-'a']+=p3-p1,
cont[p4][str[p3-1]-'a']+=p3-p1;
}
for(int i=2;i<=n;i++)
bad[0][i]+=bad[0][i-1];
for(int i=2;i<=n;i++)
bad[0][i]+=bad[0][i-1];
for(int i=n;--i;)
bad[1][i]+=bad[1][i+1];
for(int i=n;--i;)
bad[1][i]+=bad[1][i+1];
for(int i=1;i<=n;i++)for(auto j:cont[i])
ans=max(ans,j-bad[0][i]-bad[1][i]);
cout<<ans+nc;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
3160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
10 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
248 ms |
24888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |