Cod sursa(job #1441894)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 mai 2015 13:24:13
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#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;
}