Pagini recente » Cod sursa (job #607845) | Cod sursa (job #608850) | Cod sursa (job #1294539) | Cod sursa (job #1012649) | Cod sursa (job #1003440)
#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]=init[i];
sir[2*i]='*';
}
n*=2;
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];
//cout<<man[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-1); dif++)
if(sir[i+dif]!=sir[i-dif])
break;
man[i]=dif-1;
if((i+man[i])>(centru+man[centru]))
centru=i;
//cout<<man[i];
s+=(man[i]/2);
if(sir[i]!='*')
s++;
}
cout<<s<<'\n';
cin.close();
cout.close();
return 0;
}