Pagini recente » Cod sursa (job #1772689) | Cod sursa (job #1963731) | Cod sursa (job #3194006) | Cod sursa (job #1083189) | Cod sursa (job #2068963)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1000002];
int lsc[2000006],c,r,n;
int poz(int x)
{
return 2*x+1;
}
void palind()
{
c=1;
r=2;
n=2*strlen(a)+1;
bool exp;
int iMirror;
for(int i=2; i<n; i++)
{
exp=false;
iMirror=2*c-i;
lsc[i]=0;
if(r-i)
{
lsc[i]=min(lsc[iMirror],r-i);
}
while (((i + lsc[i]) < n && (i - lsc[i]) > 0) &&
( ((i + lsc[i] + 1) % 2 == 0) ||
(a[(i + lsc[i] + 1)/2] == a[(i-lsc[i]-1)/2] )))
{
lsc[i]++;
}
if(i+lsc[i]>r)
{
c=i;
r=i+lsc[i];
}
}
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",&a);
palind();
long long rasp=strlen(a);
for(int i=0; i<n; i++)
if(i%2)
rasp+=(lsc[i]-1)/2;
else
rasp+=lsc[i]/2;
printf("%lld",rasp);
return 0;
}