Pagini recente » Cod sursa (job #795558) | Istoria paginii runda/anti_avram_2 | Cod sursa (job #3129240) | Cod sursa (job #1354159) | Cod sursa (job #1789593)
#include <cstdio>
#include <cstring>
using namespace std;
int minim(long long a,long long b)
{
if(a<b) return a;
return b;
}
const int nmax=3000006;
char a[nmax],b[nmax];
long long p[nmax];
int mar,n=-1;
int main()
{
freopen ("pscpld.in","r",stdin);
freopen ("pscpld.out","w",stdout);
scanf("%s",b);
mar=strlen(b);
for(int i=0;i<mar;i++)
{
a[++n]='#';
a[++n]=b[i];
}
a[++n]='#';
int c=0,r=0;
for(int i=1;i<=n;i++)
{
int mirr=2*c-i;
if(i<r) p[i]=minim(p[mirr],(long long)r-i);
while(1)
{
if(i-p[i]-1<0) break;
if(i+p[i]+1>n) break;
if(a[i+p[i]+1]!=a[i-p[i]-1]) break;
++p[i];
}
if(i+p[i]>r)
{
c=i;
r=i+p[i];
}
}
long long sum=0;
for(int i=0;i<=n;i++)
{
if(i%2==1) sum+=p[i]/2;
else sum+=(p[i]+1)/2;
}
sum+=mar;
printf("%lld\n",sum);
return 0;
}