Pagini recente » Cod sursa (job #1097295) | Cod sursa (job #2322002) | Cod sursa (job #809932) | Cod sursa (job #1005230) | Cod sursa (job #2068883)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char cuv[2000010];
long long lp[2000010];
int centru,dr,lgmax,contor,lg,suma=1;
int mini(int a,int b)
{
if(a<b)
return a;
return b;
}
void citire()
{
cin.getline(cuv,1000005);
lg=strlen(cuv);
contor=lg;
lg=2*lg+1;
}
void cel_mai_lung()
{
lp[1]=1;
if(lg==0)
return;
for(int i=2; i<lg; i++)
{
if(dr-i>0)
lp[i]=mini(lp[2*centru-i],dr-i);
while(((i+lp[i])<lg&&(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])%2!=0)
contor++;
}
if(lp[i]>lgmax)
{
lgmax=lp[i];
//maxLPSCenterPosition = i;
}
if (i+lp[i]>dr)
{
centru=i;
dr=i+lp[i];
}
if(i%2==0)
suma+=(lp[i])/2;
else
suma+=(lp[i]+1)/2;
}
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
citire();
cel_mai_lung();
cout<<suma;
return 0;
}