Pagini recente » Cod sursa (job #603550) | Cod sursa (job #973207) | Cod sursa (job #2764978) | anaconda | Cod sursa (job #2040957)
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
char T[1000002];
char S[2000005];
int P[2000005];
int id,mx;
int n,m;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
long long rez;
int main()
{
fi>>T+1;
n=strlen(T+1);
for (int i=1;i<=n;i++)
S[2*i]=T[i];
for (int i=1;i<=2*n;i=i+2)
S[i]='*';
S[0]='+';
S[2*n+1]='*';
S[2*n+2]='-';
S[2*n+3]='\0';
m=2*n+1;
id=1;
mx=1;
P[1]=1;
for (int i=2;i<=m;i++)
{
if (i<mx)
P[i]=min(P[2*id-i],mx-i);
else
P[i]=1;
while (S[i+P[i]]==S[i-P[i]])
P[i]++;
if (i+P[i]-1>mx)
{
id=i;
mx=i+P[i]-1;
}
}
/*
for (int i=1;i<=m;i++)
cout<<S[i];
cout<<"\n";
for (int i=1;i<=m;i++)
if (i%2==1)
cout<<(P[i]-1)/2;
else
cout<<P[i]/2;
*/
rez=0LL;
for (int i=1;i<=m;i++)
if (i%2==1)
rez=rez+(P[i]-1)/2;
else
rez=rez+P[i]/2;
fo<<rez;
fi.close();
fo.close();
return 0;
}