Pagini recente » Cod sursa (job #708917) | Cod sursa (job #1376143) | Cod sursa (job #1328900) | Cod sursa (job #499023) | Cod sursa (job #1605203)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
char s[2000010];
char ax[1000010];
int p[2000010];
int main(){
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
s[0] = '$';
s[1] = '#';
scanf("%s",ax+1);
int n = strlen(ax+1);
int l = 2;
for(int i = 1;i <= n;i++){
s[l++] = ax[i];
s[l++] = '#';
}
s[l] = '@';
int R,C;
R = C = 0;
ll sum = 0;
for(int i = 1;i < l;i++){
int mirr = 2*C-i;
if(i < R){
p[i] = min(R-i, p[mirr]);
}
while(s[i+1+p[i]] == s[i-1-p[i]]){
p[i]++;
}
if(i+p[i] > R){
R = i+p[i];
C = i;
}
sum = sum+(p[i]+1)/2;
//printf("%d ",p[i]);
}
// printf("\n");
// for(int i = 1;i < l;i++){
// printf("%c ",s[i]);
// }
printf("%lld",sum);
return 0;
}