Pagini recente » Cod sursa (job #2852330) | Cod sursa (job #1618152) | Cod sursa (job #724714) | Cod sursa (job #1228007) | Cod sursa (job #2068804)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char cuv[2000010];
int lp[2000010],centru,dr,lgmax,contor,lg,suma;
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]=min(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];
}
}
}
void afisare()
{
for(int i=1; i<lg; i+=2)
suma+=lp[i];
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
citire();
cel_mai_lung();
afisare();
cout<<suma;
return 0;
}