Pagini recente » Cod sursa (job #2921658) | Cod sursa (job #2744171) | Cod sursa (job #1807230) | Cod sursa (job #2464285) | Cod sursa (job #3151655)
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
const int maxlen = 1e6 + 2;
char s[maxlen];
char a[2 * maxlen];
int d[2 * maxlen];
int sLen, N;
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", s + 1);
sLen = strlen(s + 1);
N = 2 * sLen + 1;
a[1] = '*';
for(int i = 1;i <= sLen;i++) {
a[2 * i] = s[i];
a[2 * i + 1] = '*';
}
int range, index;
range = 0,
index = 1;
long long ans = 0LL;
while(index <= N) {
range = 0;
while(index - range - 1 >= 1 && index + range + 1 <= N &&
a[index - range - 1] == a[index + range + 1])
range++;
d[index] = range;
int maxRange = range;
int oldIndex = index;
index++;
int oppositeIndex = oldIndex - 1;
while(index <= oldIndex + range && index <= N) {
maxRange--;
d[index] = std::min(d[oppositeIndex], maxRange);
while(index - d[index] - 1 >= 1 && index + d[index] + 1 <= N &&
a[index - d[index] - 1] == a[index + d[index] + 1])
d[index]++;
oppositeIndex--;
index++;
}
}
for(int i = 1;i <= N;i++)
ans += 1LL * (d[i] + 1) / 2;
printf("%lld\n", ans);
return 0;
}