Pagini recente » Cod sursa (job #2783160) | Cod sursa (job #1020936) | Cod sursa (job #293835) | Cod sursa (job #2474479) | Cod sursa (job #2068946)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int L[2000004], n;
int c=1;
int r=2, dif;
long long nr=1;
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
char a[1000000];
cin.getline(a, 1000000);
n=strlen(a);
n=n*2+1;
L[0]=0;
L[1]=1;
for(int i=2; i<=n; i++)
{
int oglindit=c*2-i;
dif=r-i;
if(dif>0)
L[i]=min(L[oglindit], dif);
while ( ((i + L[i]) < n && (i - L[i]) > 0) && ( ((i + L[i] + 1) % 2 == 0) || (a[(i + L[i] + 1)/2] == a[(i - L[i] - 1)/2] )))
L[i]++;
if(i+L[i]>r)
{
c=i;
r=i+L[i];
}
if(i%2==0)
nr+=L[i]/2;
else
nr+=(L[i]+1)/2;
}
printf("%d", nr);
return 0;
}