Pagini recente » Cod sursa (job #1497000) | Cod sursa (job #1364168) | Cod sursa (job #1649991) | Cod sursa (job #2147031) | Cod sursa (job #2068831)
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 1000005
using namespace std;
char cuv[N];
int lp[2*N+1], nr=1, n;
void rezolvare()
{
if(n==0)
return;
n=2*n+1;
lp[1]=1;
int c=1, r=2, iogl, exp, dif;
for(int i=2;i<n;i++)
{
iogl=2*c-i;
exp=0;
dif=r-i;
if(dif>0)
{
if(lp[iogl]<dif)
lp[i]=lp[iogl];
else
if(lp[iogl]==dif && i==n-1)
lp[i]=lp[iogl];
else
if(lp[iogl]==dif && i<n-1)
lp[i]=lp[iogl], exp=1;
else
if(lp[iogl]>dif)
lp[i]=dif, exp=1;
}
else
lp[i]=0, exp=1;
if(exp)
while((i+lp[i])<n && (i-lp[i])>0 && ((i+lp[i]+1)%2==0 || cuv[(i+lp[i]+1)/2]==cuv[(i-lp[i]-1)/2]))
lp[i]++;
if(i+lp[i]>r)
{
c=i;
r=i+lp[i];
}
if(i%2==0)
nr+=lp[i]/2;
else
nr+=(lp[i]+1)/2;
// printf("%d ", lp[i]);
}
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
fgets(cuv, N, stdin);
n=strlen(cuv)-1;
cuv[n]='\0';
rezolvare();
printf("%d", nr);
return 0;
}