Pagini recente » Cod sursa (job #528153) | Cod sursa (job #2841989) | Cod sursa (job #1174332) | Cod sursa (job #287965) | Cod sursa (job #1441894)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
template < typename str_t >
void find_pal_len(const str_t &str, vector< int > &lung) {
const int n = str.size();
lung.resize(n, 0);
int caracter_citit = -1;
for (int i = 0; i < n; ++i) {
caracter_citit = max(caracter_citit, i);
int j = min({lung[i], caracter_citit - i, n-i-1});
for (; i - j >= 0 && i + j < n && str[i - j] == str[i + j]; ++j){
lung[i+j] = lung[i-j]; }
lung[i] = j - 1;
for(int k = i+1; k <= i+lung[i]; ++k){
lung[k] = min(lung[k], lung[i]); }
caracter_citit = max(caracter_citit, i + lung[i]);
}
}
class string_adapter {
const string &str;
public:
string_adapter(const string &STR) : str(STR) {}
int size() const { return 2 * str.size() + 1; }
const char operator[](const int poz) const {
return poz % 2 == 0 ? '#' : str[poz / 2];
}
};
int main() {
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string str;
f >> str;
const string_adapter str_adap(str);
vector< int > lung;
find_pal_len(str_adap, lung);
transform(begin(lung), end(lung), begin(lung),
[](const int x) { return x / 2; });
g << (accumulate(begin(lung), end(lung), 0) + str.size());
return 0;
}