Pagini recente » Cod sursa (job #2794568) | Cod sursa (job #2149010) | Cod sursa (job #1489165) | Cod sursa (job #1380191) | Cod sursa (job #2068991)
#include <iostream>
#include <fstream>
#include <cstring>
#define X 2000001
using namespace std;
int LP[X],n,i,r=2,c=1,oglinda,dif;
char a[X];
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin.get(a,X);
n=strlen(a);
n=2*n+1;
LP[0]=0;
LP[1]=1;
for(int i=2;i<=n;i++)
{
oglinda=2*c-i;
dif=r-i;
if(dif>0)
LP[i]=min(LP[oglinda],dif);
while ( ((i + LP[i]) < n && (i - LP[i]) > 0) && ( ((i + LP[i] + 1) % 2 == 0) || (a[(i + LP[i] + 1)/2] == a[(i - LP[i] - 1)/2] )))
{
LP[i]++;
}
if (i + LP[i] > r)
{
c = i;
r = i + LP[i];
}
}
long long s=0;
for(int i=1;i<n;i++)
if(LP[i]%2==1)
s=s+LP[i]/2+1;
else
s=s+LP[i]/2;
fout<<s;
return 0;
}