Pagini recente » Cod sursa (job #150843) | Cod sursa (job #1306917) | Cod sursa (job #1774497) | Cod sursa (job #2973446) | Cod sursa (job #2719288)
#include <bits/stdc++.h>
using namespace std;
int manacher[2000005];
string s;
int main() {
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
ios::sync_with_stdio(false);
fin.tie(nullptr);
int middle = 0;
string input;
fin >> input;
s = "$";
s += "$";
for (auto x : input) {
s += x;
s += "$";
}
for (int i = 1; i < s.size(); ++i) {
if (i > middle + manacher[middle] / 2) {
manacher[i] = 1;
} else {
manacher[i] = min(manacher[2 * middle - i], 2 * (middle + manacher[middle] / 2 - i) + 1);
}
while (i - manacher[i] / 2 - 1 >= 1 and i + manacher[i] / 2 + 1 < s.size() and s[i - manacher[i] / 2 - 1] == s[i + manacher[i] / 2 + 1]) {
manacher[i] += 2;
}
if (middle + manacher[middle] / 2 < i + manacher[i] / 2) {
middle = i;
}
}
long long ans = 0;
for (int i = 1; i < s.size(); ++i) {
ans += (manacher[i] / 2 + 1) / 2;
}
fout << ans;
return 0;
}