Pagini recente » Cod sursa (job #148083) | Cod sursa (job #67811) | Cod sursa (job #871168) | Cod sursa (job #1185059) | Cod sursa (job #2798853)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
using ll = long long;
int main() {
in.tie(NULL);
out.tie(NULL);
ios_base::sync_with_stdio(false);
string s; in >> s;
string t;
t += 'W';
for (char c : s) {
t += c;
t += 'W';
}
vector<int> pal((int)t.size());
int l = -1, r = -1;
for (int i = 0; i < (int)t.size(); i++) {
if (i > r)
pal[i] = 1;
else
pal[i] = min(r - i + 1, pal[l + r - i]);
while (i - pal[i] >= 0 && i + pal[i] < (int)t.size() && t[i - pal[i]] == t[i + pal[i]])
pal[i]++;
pal[i]--;
if (i + pal[i] > r) {
r = i + pal[i];
l = i - pal[i];
}
}
ll ans = (ll)0;
for (int i = 0; i < (int)t.size(); i++)
ans += (ll)(1 + pal[i]) / 2;
out << ans << "\n";
return 0;
}