Pagini recente » Cod sursa (job #1120684) | Cod sursa (job #880809) | Cod sursa (job #1773634) | Cod sursa (job #1424738) | Cod sursa (job #2105678)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");
void Solve (string s) {
vector < int > pali ((int) s.size() + 1);
int R = -1, o = -1;
for (int i = 0; i < (int) s.size(); ++ i) {
if (i > R) {
o = i;
while (i - pali[i] >= 0 and s[i + pali[i]] == s[i - pali[i]] and i + pali[i] < (int) s.size()) {
++ pali[i];
}
-- pali[i];
R = i + pali[i];
continue;
}
pali[i] = pali[2 * o - i];
if (i + pali[i] < R) {
continue;
}
pali[i] = R - i;
while (i - pali[i] >= 0 and s[i + pali[i]] == s[i - pali[i]] and i + pali[i] < (int) s.size ()) {
++ pali[i];
}
-- pali[i];
if (pali[i] != R) {
R = pali[i];
o = i;
}
}
long long ans = 0;
for (int i = 0; i < (int) s.size(); ++ i) {
if (i % 2 == 0) {
ans += (pali[i] / 2 + 1);
}
else {
ans += ((pali[i] + 1) / 2);
}
}
cout << ans << '\n';
}
int main () {
ios::sync_with_stdio (false);
string inp, s;
cin >> inp;
for (auto x : inp) {
s += x;
s += '#';
}
s.pop_back ();
Solve (s);
}