Pagini recente » Cod sursa (job #2546149) | Cod sursa (job #952599) | Cod sursa (job #675164) | Cod sursa (job #585403) | Cod sursa (job #2041086)
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
char T[1000002],S[2000005];
int P[2000005];
int n,m,id,mx;
long long rez;
int main()
{
fi>>T+1;
n=strlen(T+1);
/// se formeaza S
for (int i=1;i<=n;i++)
S[2*i]=T[i];
for (int i=1;i<=2*n+1;i=i+2)
S[i]='*';
S[0]='+';
S[2*n+2]='-';
S[2*n+3]='\0';
m=2*n+1;
P[1]=1;
id=1;
mx=1;
for (int i=2;i<=m;i++)
{
if (i<=mx)
P[i]=min(P[2*id-i],mx-i+1);
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++)
fo<<S[i];
fo<<"\n";
for (int i=1;i<=m;i++)
fo<<P[i];
*/
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;
}