Pagini recente » Istoria paginii utilizator/meharges20e | Rezultatele filtrării | Rezultatele filtrării | Borderou de evaluare (job #32357) | Cod sursa (job #2722461)
#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 && i + m[mij - (i - mij)] < r) {
m[i] = m[mij - (i - mij)];
continue;
}
int x = 0;
if (i < r)
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;
}
}
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;
}