Pagini recente » Cod sursa (job #1341745) | Cod sursa (job #3270790) | Cod sursa (job #1176967) | Cod sursa (job #3283872) | Cod sursa (job #1065346)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
char A[1000001];
char X[2000005];
int n,i;
int P[2000005];
int id,mx;
long long rez;
int main()
{
fi>>A;
X[0]='$';
X[1]='#';
n=2;
for (i=0;A[i]!='\0';i++)
{
X[n++]=A[i];
X[n++]='#';
}
X[n]='\0';
P[0]=1;
P[1]=1;
id=1;
mx=1;
for (i=2;i<n;i++)
{
P[i]= mx > i ? min(P[2*id-i], mx-i) : 1;
while (X[i + P[i]] == X[i - P[i]])
P[i]++;
if (i + P[i] > mx)
{
mx = i + P[i];
id = i;
}
}
rez=0;
for(i=1;i<n;i++)
rez+=(P[i]/2);
fo<<rez<<'\n';
fi.close();
fo.close();
return 0;
}