Pagini recente » Cod sursa (job #2368425) | Cod sursa (job #582377)
Cod sursa(job #582377)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_N 2000010
int n;
long long sol;
int d[MAX_N];
char s[MAX_N / 2], A[MAX_N];
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", s);
int L = strlen(s);
for (int i = 0; i < L; i++) {
A[++n] = s[i];
if (i != L - 1)
A[++n] = '@';
}
for (int i = 1; i <= n; i++) {
if (i == 1)
d[i] = 1;
else
d[i] = min(d[i - 2], d[i - 1] - 1);
int left = i - d[i], right = i + d[i];
while (0 < left && right <= n && A[left] == A[right]) {
d[i]++;
left--;
right++;
}
if (A[i] == '@')
sol += d[i] / 2;
else
sol += (d[i] + 1) / 2;
}
printf("%lld\n", sol);
return 0;
}