Pagini recente » Cod sursa (job #1110872) | Cod sursa (job #1104617) | Cod sursa (job #222814) | Cod sursa (job #3244252) | Cod sursa (job #2722443)
#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 = 1, mij = 1;
for (int i = 2; i <= n; ++i) {
int x = 0;
if (i <= r)
x = m[mij - (i - mij)];
while (x < i && i + x + 1 <= n && s[i + x + 1] == s[i - x - 1])
++x;
m[i] = x;
if (i + x > r) {
r = i + x;
mij = i;
}
}
}
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();
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (i & 1) { //litera
ans += m[i] / 2 + 1;
} else { //*
ans += (m[i] + 1) / 2;
}
}
cout << ans;
return 0;
}