Pagini recente » Cod sursa (job #1335413) | Cod sursa (job #1550910) | Cod sursa (job #1482516) | Cod sursa (job #1970271) | Cod sursa (job #297999)
Cod sursa(job #297999)
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "pscpld.in"
#define FOUT "pscpld.out"
#define MAX_N 1000005
char A[MAX_N];
int P[MAX_N << 1], L[MAX_N << 1], R[MAX_N << 1];
int N;
inline int ins (int c, int d)
{
if (c - d >= 0 && c + d <= N) return 1;
return 0;
}
inline int insp (int c, int d)
{
if (c - d >= 0 && c + d + 1 <= N) return 1;
return 0;
}
void solve ()
{
int i, m, mp, d, c;
P[1] = 1, m = mp = 1;
L[1] = R[1] = 1;
for (i = 2; i < N << 1; ++i)
{
if (i & 1) // impar
{
P[i] = 1;
if (m >= i)
{
P[i] = P[(mp << 1) - i];
if (L[(mp << 1) - i] < L[mp] && L[(mp << 1) - i]) P[i] -= (L[mp] - L[(mp << 1) - i]) << 1;
}
d = (P[i] >> 1) + 1;
c = (i + 1) >> 1;
while (A[c - d] == A[c + d] && ins(c, d)) P[i] += 2, ++d;
--d;
L[i] = c - d, R[i] = c + d;
if (!P[i]) L[i] = R[i] = 0;
}
else
{
if (m >= i)
{
P[i] = P[(mp << 1) - i];
if (L[(mp << 1) - i] < L[mp] && L[(mp << 1) - i]) P[i] -= (L[mp] - L[(mp << 1) - i]) << 1;
}
d = P[i] >> 1;
c = (i + 1) >> 1;
while (A[c - d] == A[c + d + 1] && insp(c, d)) P[i] += 2, ++d;
--d;
L[i] = c - d, R[i] = c + d + 1;
if (!P[i]) L[i] = R[i] = 0;
}
if ((R[i] << 1) - 1 > m) m = (R[i] << 1) - 1, mp = i;
}
long long BEST = 0;
for (i = 1; i < N << 1; ++i)
{
if (!P[i]) continue;
if (i & 1) BEST += P[i] / 2 + 1;
else BEST += P[i] / 2;
}
printf ("%lld\n", BEST);
// for (i = 1; i <= N; ++i)
// printf ("%d ", P[i]);
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
gets (A + 1);
N = strlen (A + 1);
solve ();
return 0;
}