Pagini recente » Cod sursa (job #1379046) | Cod sursa (job #2655599) | Cod sursa (job #66876) | Cod sursa (job #2584234) | Cod sursa (job #2798859)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
using ll = long long;
int main() {
in.tie(NULL);
ios_base::sync_with_stdio(false);
char c;
string t = "W";
while (in >> c) {
t += c;
t += 'W';
}
vector<int> pal((int)t.size());
ll ans = (ll)0;
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];
}
ans += (ll)(1 + pal[i]) / 2;
}
out << ans << "\n";
return 0;
}