Pagini recente » Cod sursa (job #1031218) | Cod sursa (job #2799869) | Cod sursa (job #865122) | Cod sursa (job #2137319) | Cod sursa (job #1168994)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<sstream>
#include<iostream>
#include <iomanip>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define pb push_back
using namespace std;
char s[2010000];
char s1[2010000];
int val[2020201];
int maxind,maxVal,N;
long long S=0;
void make_sir(){
s1[0]='*';
for(int i=1;i<=N;++i){
s1[i*2-1]=s[i];
s1[i*2]='*';
}
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",s+1);
N = strlen(s+1);
make_sir();
for(int i=1;i<2*N;++i)
{
if(maxVal >= i){
int loc = maxind - (i-maxind);
val[i] = min(val[loc],maxVal-i);
}
//printf("%c %c %c\n",s1[i],s1[i-val[i]-1],s1[i+val[i]+1]);
while((i - val[i] >= 0) && (i + val[i] <= 2*N) && (s1[i-val[i]] == s1[i+val[i]])){
++val[i];
if(i + val[i] > maxVal){
maxVal = i + val[i];
maxind = i;
}
}
}
for(int i=1;i<2*N;++i){
//printf("%d %c\n",val[i],s1[i]);
S+=(val[i]+1)/2;
if(s1[i]=='*')
--S;
}
printf("%lld",S);
return 0;
}