Pagini recente » Cod sursa (job #2818903) | Cod sursa (job #2857611) | Cod sursa (job #560511) | Cod sursa (job #1398276) | Cod sursa (job #1621634)
#include <cstdio>
#include <cstring>
using namespace std;
const int nmax = 1000007;
int n;
int d[nmax * 2];
char s[nmax * 2];
char w[nmax];
long long manacher() {
long long ans = 0;
for (int i = 1, j = 0; i <= n; i++) {
s[++j] = w[i];
s[++j] = '#';
}
n = 2*n;
int l = 0, r = 0, c = 0;
for (int i = 1; i <= n; i++) {
if (i <= r) {
int j = 2 * c - i;
if (j - d[j] > l) {
d[i] = d[j];
} else {
d[i] = j - l;
}
} else {
d[i] = 0;
}
while (i + d[i] <= n && i - d[i] >= 1) {
if (s[i + d[i]] != s[i - d[i]])
break;
d[i]++;
}
if (i + d[i] > r) {
c = i;
r = i + d[i];
l = i - d[i];
}
}
for (int i = 1; i <= n; i++) {
if (s[i] == '#')
ans += d[i]/2;
else
ans += (d[i] + 1)/2;
}
return ans;
}
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", w + 1);
n = strlen(w + 1);
printf("%lld\n", manacher());
return 0;
}