Pagini recente » Cod sursa (job #648150) | Cod sursa (job #1653094) | Cod sursa (job #1033920) | Cod sursa (job #2709444) | Cod sursa (job #2864046)
#include <bits/stdc++.h>
using namespace std;
void manacher(const string& s, vector<int>& z) {
int l = 0, r = -1;
z[0] = 0;
for (int i = 1; i < s.size(); ++i) {
z[i] = 0;
if (i <= r)
z[i] = min(z[l + (r - i)], r - i + 1);
while (i + z[i] < s.size() && i - z[i] >= 0 && s[i + z[i]] == s[i - z[i]])
++z[i];
if (i + z[i] - 1 > r) {
l = i - z[i] + 1;
r = i + z[i] - 1;
}
}
}
int main() {
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
string a;
cin >> a;
cin.close();
string s = "#";
for (int i = 0; i < a.size(); ++i) {
s.push_back(a[i]);
s.push_back('#');
}
vector<int> z(s.size());
manacher(s, z);
long long ans = 0;
for (auto i: z)
ans += i / 2;
cout << ans << "\n";
cout.close();
return 0;
}