Pagini recente » Cod sursa (job #318273) | Cod sursa (job #2162965) | Cod sursa (job #2739794) | Cod sursa (job #3185394) | Cod sursa (job #2232015)
#include <cstdio>
#include <cstring>
using namespace std;
int d[2000005];
char s[2000005];
int min(const int& a, const int& b) {
return (a < b) ? a : b;
}
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int n = 0;
s[n++] = '+';
while (scanf("%c", &s[n++]) > 0)
s[n++] = '+';
long long res = 0;
int l = 0, r = -1;
int k;
for (int i = 0; i < n; ++i) {
d[i] = (i > r) ? 1 : min(d[l + (r - i)], r - i);
while (0 <= i - d[i] && i + d[i] < n && s[i - d[i]] == s[i + d[i]])
++d[i];
k = d[i] - 1;
if (i + k > r) {
l = i - k;
r = i + k;
}
res += d[i] / 2;
}
printf("%lld", res);
return 0;
}