Pagini recente » Cod sursa (job #872738) | Cod sursa (job #169814) | Cod sursa (job #2574261) | Cod sursa (job #1296482) | Cod sursa (job #2574249)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main() {
string str; fin >> str;
int n = str.size();
vector<int> d1(n);
for (int i = 0, l = 0, r = 0; i < n; i++) {
int x = i, y = i;
if (r >= i) {
x = max(l, i - d1[l + r - i] / 2);
y = min(r, i + d1[l + r - i] / 2);
}
for (; 0 <= x - 1 && y + 1 < n && str[x - 1] == str[y + 1]; x--, y++);
d1[i] = y - x + 1;
if (y > r) {
l = x;
r = y;
}
}
vector<int> d2(n);
for (int i = 1, l = 1, r = 0; i < n; i++) {
int x = i, y = i - 1;
if (r >= i) {
x = max(l, i - d2[l + r - i] / 2);
y = min(r, i + d2[l + r - i] / 2 - 1);
}
for (; 0 <= x - 1 && y + 1 < n && str[x - 1] == str[y + 1]; x--, y++);
d2[i] = y - x + 1;
if (y > r) {
l = x;
r = y;
}
}
int64_t cnt = 0;
for (int i = 0; i < n; i++)
cnt += d1[i] / 2 + d2[i] / 2 + 1;
fout << cnt << '\n';
fout.close();
return 0;
}