Pagini recente » Cod sursa (job #2006190) | Cod sursa (job #2902271) | Profil georeginfoarena | Cod sursa (job #3166469) | Cod sursa (job #1003498)
#include <fstream>
#include <cstring>
using namespace std;
char sir[2000010];
int man[2000010];
char init[1000005];
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
cin.get(init,1000005);
int n=strlen(init),dif,i,centru=0;
long long int s=0;
for(i=n; i>=1; i--)
init[i]=init[i-1];
for(i=1;i<=n;i++)
{
sir[2*i-1]='*';
sir[2*i]=init[i];
}
sir[2*n+1]='*';
n*=2;
n++;
for(i=1; i<=n; i++)
{
if((centru+man[centru])<i)
dif=1;
else if((2*centru-i-man[2*centru-i])>(centru-man[centru]))
{
man[i]=man[2*centru-i];
s+=(man[i]/2);
if(sir[i]!='*')
s++;
continue;
}
else
dif=2*centru-i-(centru-man[centru])+1;
for(; ((i-dif)>=1) && ((i+dif)<=n) && dif<n; dif++)
if(sir[i+dif]!=sir[i-dif])
break;
man[i]=dif-1;
if((i+man[i])>(centru+man[centru]))
centru=i;
s+=(man[i]/2);
if(sir[i]!='*')
s++;
}
cout<<s<<'\n';
cin.close();
cout.close();
return 0;
}