Pagini recente » Cod sursa (job #3195027) | Cod sursa (job #716031) | Cod sursa (job #2408928) | Cod sursa (job #1716171) | Cod sursa (job #2608159)
#include <stdio.h>
#include <iostream>
#define L 1000003
using namespace std;
int s[L], d1[L], d2[L];
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
long long rez;
int i=0, n, k, l, r;
char c;
while ( (c = fgetc(stdin))!='\n')
s[i++] = c;
n = i;
for (i = 0, l = 0, r = -1; i < n; i++) {
k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k])
k++;
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
for (i = 0, l = 0, r = -1; i < n; i++) {
k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k])
k++;
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k ;
}
}
rez = 0;
for (i = 0; i < n; i++)
rez += d1[i] + d2[i];
printf("%lld\n", rez);
return 0;
}