Pagini recente » Cod sursa (job #3192731) | Cod sursa (job #1179302) | Cod sursa (job #1358864) | Cod sursa (job #727187) | Cod sursa (job #446491)
Cod sursa(job #446491)
#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;
FILE *fin = freopen(FIN, "r", stdin), *fout = freopen(FOUT, "w", stdout);
for (char c = getchar(); c >= 'a' && c <= 'z'; c = getchar()) sz[++dim] = c;
/*for (int i = 1; i <= (dim << 1) - 1; i += 2) lg[i] = 1;
for (int i = 1, l, r; i <= (dim << 1) - 1; ++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;
while (l && (r - dim - 1))
if (sz[l] == sz[r]) --l, ++r, lg[i] += 2;
else break;
++l; --r;
for (int il = (l << 1) - 1, ir = (r << 1) - 1; il < ir; ++il, --ir)
if (il & 1) lg[ir] = max(lg[ir], min(lg[il], min(i - il + 1, il - (l << 1))));
else lg[ir] = max(lg[ir], min(lg[il], min(i - il + 1, il - (l << 1) + 2)));
ret += ((long long)lg[i] + 1) >> 1;
}*/
for (int i = 1, l, r; i <= dim; ++i)
{
l = i; r = i;
while (l && (r - dim - 1))
{
if (sz[l] == sz[r]) ++ret, --l, ++r;
else break;
}
l = i - 1; r = i;
while (l && (r - dim - 1))
{
if (sz[l] == sz[r]) ++ret, --l, ++r;
else break;
}
}
printf("%lld\n", ret);
return 0;
}