Pagini recente » Cod sursa (job #2798703) | Cod sursa (job #2059180) | Cod sursa (job #2798866) | Cod sursa (job #990278) | Cod sursa (job #2942018)
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int t[1000001];
signed main() {
string basic, s;
int i, drmax, curCenter, lung, st, dr, rez;
drmax = 0;
curCenter = 0;
cin >> basic;
for (i = 0; i < basic.size(); i++) {
s = s + '#' + basic[i];
}
lung = s.size() - 1;
for (i = 1; i <= lung; i++) {
if (i <= drmax) {
st = i - t[curCenter - (i - curCenter)];
dr = i + t[curCenter - (i - curCenter)];
}
else {
st = i;
dr = i;
}
while (dr + 1 <= lung && st - 1 >= 1 && s[st - 1] == s[dr + 1]) {
st--;
dr++;
}
t[i] = dr - i;
if (dr > drmax) {
drmax = dr;
curCenter = i;
}
}
rez = 0;
for (i = 1; i <= lung; i++) {
if (i % 2 == 1) {
rez = rez + t[i] / 2 + 1;
}
else {
rez = rez + (t[i] + 1) / 2;
}
}
cout << rez;
return 0;
}