Pagini recente » Istoria paginii utilizator/matei20050715 | Istoria paginii utilizator/teofil2003 | Istoria paginii utilizator/romeo37 | Statistici Renata (Mondiala) | Cod sursa (job #1303232)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 1000005
using namespace std;
char c[Nmax],a[Nmax*2];
int DP[Nmax*2];
int nr,N;
long long ans;
void read()
{
fgets(c+1,Nmax,stdin);
c[0]='#';
if(c[strlen(c)-1] == '\n')
c[strlen(c)-1] = 0;
nr = strlen(c+1);
}
void expand()
{
a[N++] = '&';
a[N] = '#';
for(int i = 1 ; i <= nr; ++i)
{
a[++N] = c[i];
a[++N] = '#';
}
a[++N] = '$';
}
void manacher()
{
DP[1] = 1;
int center,right,_i;
center = right = 0;
for(int i = 1; i < N; ++i)
{
_i = 2*center - i;
DP[i] = (i < right) ? min(DP[_i],right - i) : 1;
while(a[i - DP[i]] == a[i + DP[i]])
++DP[i];
if(center + DP[i] > right){
right = center + DP[i];
center = i;
}
ans += DP[i] / 2;
}
printf("%lld\n",ans);
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
read();
expand();
manacher();
return 0;
}