Pagini recente » Cod sursa (job #752047) | Cod sursa (job #2449500) | Cod sursa (job #922637) | Cod sursa (job #1030102) | Cod sursa (job #893785)
Cod sursa(job #893785)
#include<cstring>
#include<cstdio>
#define NMAX 1000000+5
using namespace std;
char s[NMAX];
int i,j,l,r,p[2*NMAX],q[2*NMAX],n;
long long sol;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
s[0]='*'; s[n+1]='#';
p[1]=1;
if(s[1]==s[2]) p[2]=2;
for(i=3;i<=2*n-1;i++)
{
if(i%2==0) //palindrom de lungime para
{
if(q[i]) {l=(i-p[q[i]]+2)/2; r=p[q[i]]-1+l;}
else {l=i/2; r=i/2+1;}
}
else //palindrom de lungime impara
{
if(q[i]) {l=(i-p[q[i]]+2)/2; r=p[q[i]]-1+l;}
else l=r=i/2;
}
for(;s[l]==s[r];l--,r++)
{
if(p[2*l-1]>p[q[2*r-1]]) q[2*r-1]=2*l-1;
if(p[2*l]>p[q[2*r]]) q[2*r]=2*l;
}
l++, r--;
p[i]=r-l+1;
sol+=(p[i]+1)/2;
}
/*for(i=1;i<=2*n-1;i++) printf("%d ",p[i]);
printf("\n");
for(i=1;i<=2*n-1;i++) printf("%d ",q[i]);
printf("\n");*/
printf("%lld\n",sol+1);
return 0;
}