Pagini recente » Cod sursa (job #2733131) | Cod sursa (job #765302) | Cod sursa (job #2389622) | Cod sursa (job #594611) | Cod sursa (job #446526)
Cod sursa(job #446526)
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <ctime>
#define FIN "pscpld.in"
#define FOUT "pscpld.out"
#define NMAX 1000010
using namespace std;
char sz[NMAX];
int lg[NMAX * 2], dim = 0;
int main()
{
long long ret = 0;
int i, l, r, mirror, tmp;
char c;
FILE *fin = freopen(FIN, "r", stdin), *fout = freopen(FOUT, "w", stdout);
for (c = getchar(); c >= 'a' && c <= 'z'; c = getchar()) sz[++dim] = c;
for (i = 1, mirror = 0; i <= (dim << 1) - 1; ++i)
{
lg[i] = mirror + lg[mirror] <= i ? (i & 1 ? 1 : 0)
: min(lg[(mirror << 1) - i], mirror + lg[mirror] - i);
if (i & 1) l = ((i + 1) >> 1) - ((lg[i] + 1) >> 1) , r = ((i + 1) >> 1) + ((lg[i] + 1) >> 1);
else l = (i - lg[i]) >> 1, r = ((i + lg[i]) >> 1) + 1;
tmp = l;
while (l > 0 && (r <= dim))
if (sz[l] == sz[r]) --l, ++r;
else break;
lg[i] += (tmp - l) << 1;
mirror = mirror + lg[mirror] < i + lg[i] ? i : mirror;
ret += ((long long)lg[i] + 1) >> 1;
}
printf("%lld\n", ret);
return 0;
}