Pagini recente » Cod sursa (job #2255856) | Cod sursa (job #1972003) | Cod sursa (job #1520713) | Cod sursa (job #44304) | Cod sursa (job #3155812)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");
std::string str;
std::vector<int> manacher_odd(const std::string& str) {
std::vector<int> ret(str.size(),0);
int l = 0, r = 0;
for (int i = 0; i < str.size(); i++) {
ret[i] = std::max(0,std::min(r-i,ret[l+r-i]));
while (i-ret[i]>=0&&i+ret[i]<str.size()&&str[i-ret[i]]==str[i+ret[i]]) {
++ret[i];
}
if (i+ret[i]>r) {
l = i-ret[i];
r = i+ret[i];
}
}
return ret;
}
std::vector<int> manacher(const std::string& str) {
std::string tmp = "#";
for (const auto& i : str) {
tmp += i;
tmp += '#';
}
return manacher_odd(tmp);
}
int main() {
fin >> str;
std::vector<int> lps = manacher(str);
int64_t ret = 0;
for (int i = 0; i < lps.size(); i++) {
ret += lps[i]/2;
//std::cout << lps[i]/2 << " ";
}
//std::cout << "\n";
fout << ret << "\n";
}