Pagini recente » Cod sursa (job #1188326) | Cod sursa (job #619898) | Cod sursa (job #581531) | Rating Cucos-Artene George-Emanuel (Dietzer) | Cod sursa (job #3220749)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
vector<int> menacher(string s) {
int l = 0, r = 0;
vector<int> man(s.size());
for(int i = 0; i < (int)s.size(); i++) {
man[i] = max(0, min(r-i, man[l+r-i]));
while(i - man[i] >= 0 && i + man[i] < (int)s.size() && s[i - man[i]] == s[i + man[i]]) {
man[i]++;
}
if(i + man[i] > r) {
l = i - man[i];
r = i + man[i];
}
}
return man;
}
int main() {
string s;
in >> s;
string t;
for(auto c : s) {
t += string("#") + c;
}
t += "#";
vector<int> man = menacher(t);
int cnt = 0;
for(int i = 0; i < (int)man.size(); i++) {
cnt += man[i] / 2;
}
out << cnt;
return 0;
}