Cod sursa(job #1441813)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 mai 2015 12:43:57
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#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);
		for( ; i-j >= 0
				&& i+j < n
				&& str[i-j] == str[i+j]; ++j);
		lung[i] = j-1;
		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; }