Pagini recente » Cod sursa (job #2958274) | Cod sursa (job #2138422) | Cod sursa (job #579367) | Cod sursa (job #1210594) | Cod sursa (job #2037011)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
void Make(string &s, string in_str) {
for (auto x : in_str) {
s += x;
s += '$';
}
}
bool is_good(int cnt, int i, int len) {
return i + cnt < len and i - cnt >= 0;
}
void Solve(string s, vector < int > &pali, int &poz, int &max_r) {
int len = s.size();
for (int i = 0; i < len; i ++) {
if (i >= max_r) {
int cnt = 0;
while (is_good(cnt, i, len)) {
if (s[i + cnt] == s[i - cnt]) {
cnt ++;
continue;
}
break;
}
cnt -= 1;
pali[i] = cnt;
max_r = i + cnt;
poz = i;
continue;
}
int k = pali[2 * poz - i];
if (i + k < max_r) {
pali[i] = pali[2 * poz - i];
continue;
}
int cnt = max_r - i + 1;
while (is_good(cnt, i, len)) {
if (s[i + cnt] == s[i - cnt]) {
cnt ++;
continue;
}
break;
}
cnt -= 1;
if (cnt) {
pali[i] = cnt;
max_r = i + pali[i];
poz = i;
}
}
for (int i = 0; i < len; i ++) {
if (i % 2 == 0) {
pali[i] = 1 + pali[i] / 2;
}
else {
pali[i] = (pali[i] + 1) / 2;
}
}
}
int main(int argc, char const *argv[]) {
string in_str, s;
cin >> in_str;
Make(s, in_str);
vector < int > pali(s.size() + 7);
int poz = -1, max_r = -1;
Solve(s, pali, poz, max_r);
int sol = 0;
for (int i = 0; i < s.size(); i ++) {
sol += pali[i];
}
cout << sol << '\n';
}