Pagini recente » Cod sursa (job #660144) | Cod sursa (job #480272) | Cod sursa (job #100691) | Cod sursa (job #2711074) | Cod sursa (job #2068972)
/**#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char cuv[2000010];
int lp[2000010];
int centru=2,dr=1,lgmax,contor,lg,og,dif;
long long suma=1;
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++)
{
og=2*centru-i;
dif=dr-i;
if(dr-i>0)
lp[i]=min(lp[og],dif);
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]>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;
}
*/
#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;
long long s=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];
}
if(LP[i]%2==1)
s=s+LP[i]/2+1;
else
s=s+LP[i]/2;
}
fout<<s;
return 0;
}