Pagini recente » Cod sursa (job #627906) | Cod sursa (job #3262735) | Cod sursa (job #701805) | Cod sursa (job #1210722) | Cod sursa (job #2722455)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");
int n;
int m[2000010];
string s, s_aux;
void manacher() {
int r = 0, mij = 0;
for (int i = 1; i <= n; ++i) {
if (i < r) {
if (m[mij - (i - mij)] + i < r)
m[i] = m[mij - (i - mij)];
else {
int x = r - i;
while (s[i + x + 1] == s[i - x - 1])
++x;
if (i + x > r)
r = i + x, mij = i;
m[i] = x;
}
} else {
int x = 0;
while (s[i + x + 1] == s[i - x - 1])
++x;
r = i + x, mij = i;
m[i] = x;
}
}
}
int main() {
cin >> s_aux;
s = "#";
for (int i = 0; i < s_aux.size() - 1; ++i) {
s += s_aux[i];
s += "*";
}
s += s_aux[s_aux.size() - 1];
s += "$";
n = s.size() - 2;
manacher();
long long ans = 0;
for (int i = 1; i <= n; ++i) {
if (i & 1) { //litera
ans += (long long)(m[i] / 2 + 1);
} else { //*
ans += (long long)((m[i] + 1) / 2);
}
}
cout << ans;
return 0;
}