Pagini recente » Cod sursa (job #868242) | Cod sursa (job #2012863) | Cod sursa (job #677935) | Cod sursa (job #2443447) | Cod sursa (job #2719295)
#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 += "$";
}
long long ans = 0;
for (int i = 1; i < s.size(); ++i) {
if (i > middle + manacher[middle]) {
manacher[i] = 0;
} else {
manacher[i] = min(manacher[2 * middle - i], middle + manacher[middle] - i);
}
while (i - manacher[i] - 1 >= 1 and i + manacher[i] + 1 < s.size() and s[i - manacher[i] - 1] == s[i + manacher[i] + 1]) {
manacher[i] += 1;
}
if (middle + manacher[middle] < i + manacher[i]) {
middle = i;
}
ans += (manacher[i] + 1) / 2;
}
fout << ans;
return 0;
}