Pagini recente » Cod sursa (job #1909591) | Cod sursa (job #2901441) | Cod sursa (job #2645166) | Cod sursa (job #3032115) | Cod sursa (job #2942046)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int t[2000005];
char s[2000005];
signed main() {
char ch;
int i, curCenter, lung;
long long rez;
curCenter = 0;
lung = 0;
while(cin>>ch) {
s[lung] = '#';
lung++;
s[lung] = ch;
lung++;
}
s[lung] = '#';
for (i = 1; i <= lung; i++) {
if (i <= curCenter + t[curCenter]) {
t[i] = min(t[2 * curCenter - i], curCenter + t[curCenter] - i);
}
else {
t[0] = 0;
}
while (i + t[i] + 1 <= lung && i - t[i] - 1 >= 0 && s[i - t[i] - 1] == s[i + t[i] + 1]) {
t[i]++;
}
if (i + t[i] > curCenter + t[curCenter]) {
curCenter = i;
}
}
rez = 0;
for (i = 1; i <= lung; i++) {
if (i % 2 == 1) {
rez = rez + (long long)t[i] / 2 + 1;
}
else {
rez = rez + (long long)t[i] / 2;
}
}
cout << rez;
return 0;
}