Pagini recente » Cod sursa (job #871124) | Cod sursa (job #2075766) | Cod sursa (job #2352497) | Cod sursa (job #1281546) | Cod sursa (job #2105679)
#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];
R = i + 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 s;
s.reserve (1e6 + 7);
char c;
while (cin >> c) {
s += c;
s += '#';
}
s.pop_back ();
Solve (s);
}