Pagini recente » Cod sursa (job #905173) | Cod sursa (job #528013) | Cod sursa (job #298542) | Cod sursa (job #3273761) | Cod sursa (job #601555)
Cod sursa(job #601555)
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX_N 1000005
char A[MAX_N];
int P[MAX_N << 1];
int L[MAX_N << 1];
int N;
inline bool extendable (int l1, int l2, int side) {
if (l1 - side > 0 && l2 + side <= N && A[l1 - side] == A[l2 + side]) return 1;
return 0;
}
int main () {
freopen ("pscpld.in", "r", stdin);
freopen ("pscpld.out", "w", stdout);
gets (A + 1);
N = strlen (A + 1);
P[1] = 1;
int m = 1, mp = 1;
for (int i = 2; i <= N << 1; ++i) {
P[i] = (i & 1) ? 1 : 0;
if (i <= m) {
P[i] = P[2*mp - i];
if (L[2*mp - i] < L[mp] && L[2*mp - i]) P[i] -= 2*(L[mp] - L[2*mp - i]);
}
int side = (i & 1) ? P[i]/2 : P[i] / 2 - 1;
int l1 = (i & 1) ? (i + 1)/2 : i / 2;
int l2 = (i & 1) ? (i + 1)/2 : i / 2 + 1;
++side; while (extendable(l1, l2, side)) ++side, P[i] += 2; --side;
if ((l2 + side)*2 - 1 > m) m = (l2 + side)*2 - 1, mp = i;
L[i] = P[i] ? l1 - side : 0;
}
long long Answer = 0;
for (int i = 1; i < N << 1; ++i) {
if (!P[i]) continue;
Answer += (i & 1) ? P[i]/2 + 1 : P[i]/2;
}
printf ("%lld\n", Answer);
return 0;
}