Pagini recente » Cod sursa (job #217805) | Cod sursa (job #2999755) | Cod sursa (job #2198951) | Cod sursa (job #2620419) | Cod sursa (job #2292205)
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;
const int nMax = 2000005;
void Manacher(char v[], int sz, int ret[])
{
int R = -1, C = 0, rad;
for(int i = 0; i < sz; ++i)
{
if(i <= R)
rad = min(ret[2 * C - i], R - i) + 1;
else
rad = 0;
while(i - rad >= 0 && i + rad < sz && v[i-rad] == v[i+rad])
rad++;
ret[i] = rad - 1;
if(i + ret[i] - 1 > R)
{
C = i;
R = i + ret[i] - 1;
}
}
}
int n;
char a[nMax];
char t[nMax];
int pal[nMax];
int main()
{
ifstream in("pscpld.in");
in >> t;
in.close();
n = strlen(t);
for(int i = 0; i <= n; ++i)
a[2 * i] = '#', a[2 * i + 1] = t[i];
n = 2 * n + 1;
Manacher(a, n, pal);
long long rasp = 0;
for(int i = 0; i < n; ++i)
rasp += (1LL * (pal[i]+1) / 2);
ofstream out("pscpld.out");
out << rasp;
out.close();
return 0;
}