Pagini recente » Cod sursa (job #1958033) | Rating Popescu Ion (2H2O) | Cod sursa (job #668593) | Cod sursa (job #1955851) | Cod sursa (job #1873587)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 1000050
using namespace std;
char s[MAXN];
char s2[2*MAXN];
void build()
{
for (int i = 0, t = 2*strlen(s)+1; i < t; i++)
if (i & 1)
s2[i] = s[i>>1];
else
s2[i] = '*';
}
int p[2*MAXN];
long long sol;
void solve()
{
int r = 0, st, dr, c;
for (int i = 1, t = strlen(s2); i < t; i++) {
if (i > r) {
st = i-1;
dr = i+1;
}
else {
int mir = (c<<1)-i;
if (i+p[mir] < r) {
p[i] = p[mir];
st = -1;
}
else {
p[i] = r-i;
st = i - p[i]-1;
dr = i + p[i]+1;
}
}
while (st >= 0 && dr < t && s2[st] == s2[dr])
st--, dr++, p[i]++;
if (i+p[i] > r) {
r = i+p[i];
c = i;
}
sol += (p[i]+1)>>1;
}
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(s);
build();
solve();
printf("%lld", sol);
return 0;
}