Pagini recente » Cod sursa (job #432913) | Profil silaghi_raul | Cod sursa (job #1120495) | Cod sursa (job #1548084) | Cod sursa (job #3288569)
#include <bits/stdc++.h>
using namespace std;
string s;
string t;
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> s;
t += "$";
t += "#";
for(auto i : s) {
t += i;
t += "#";
}
t += "^";
auto manacher = [](string t) {
int ans = 0;
int le = 1, ri = 1; //am o secventa palindromica (le + 1 ... ri - 1)
vector<int>sz(t.size() + 1, 0);
//sz[i] -> cate secvente palindromice au mijlocul in i
for(int i = 1; i < t.size(); i++) {
sz[i] = max(0, min(sz[le + (ri - i)], ri - i));
while(t[i - sz[i]] == t[i + sz[i]]) { sz[i]++; }
le = min(le, i - sz[i]);
ri = max(ri, i + sz[i]);
ans += (sz[i]) / 2;
}
cout << ans;
};
manacher(t);
}