Pagini recente » Cod sursa (job #2036718) | Cod sursa (job #2353314) | Cod sursa (job #1004406) | Monitorul de evaluare | Cod sursa (job #2008802)
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;
const int nMax = 2000005;
void Manacher(char v[], int sz, int ret[])
{
ret[0] = 0;
int st, dr;
for(int i = 1; i < sz-1; ++i)
{
if(v[i-1] == v[i+1])
{
st = i - ret[i-1];
dr = i + ret[i-1];
ret[i] = ret[i-1] - 1;
while(st >= 0 && dr < sz && v[st--] == v[dr++])
ret[i]++;
}
else
ret[i] = 0;
}
ret[sz-1] = 0;
}
int n;
char a[nMax];
char t[nMax];
int pal[nMax];
int main()
{
/* ifstream in("pscpld.in");
in >> t;
in.close();*/
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
fgets(t, sizeof(t), stdin);
n = strlen(t) - 1;
for(int i = 0; i < n; ++i)
a[2 * i] = t[i], a[2 * i + 1] = '#';
n = 2 * n - 1;
Manacher(a, n, pal);
long long rasp = 0;
for(int i = 0; i < n; i += 2)
rasp += (1LL * pal[i] / 2) + 1;
for(int i = 1; i < n; i += 2)
rasp += (1LL * pal[i] / 2);
printf("%lld", rasp);
/* ofstream out("pscpld.out");
out << rasp;
out.close();*/
return 0;
}