Cod sursa(job #1499412)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 10 octombrie 2015 16:29:23
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void pscpld(const string& str, vector<int>& v){
	const int n = str.size();
	int poz_max = -1, centru_poz_max = 0;
	for(int i = 0; i < n; ++i){
		if(i > poz_max){
			int j = 1;
			for( ; 0 <= i-j && i+j < n && str[i-j] == str[i+j]; ++j);
			--j;
			v[i] = j;
			if(i+j >= poz_max){
				poz_max = i+j;
				centru_poz_max = i; } }
		else{
			const int val_omolog = v[2*centru_poz_max - i];
			if(i+val_omolog < poz_max){
				v[i] = val_omolog; }
			else{
				int j = poz_max - i;
				for( ; 0 <= i-j && i+j < n && str[i-j] == str[i+j]; ++j);
				--j;
				v[i] = j;
				if(i+j >= poz_max){
					poz_max = i+j;
					centru_poz_max = i; } } } } }

int main(){
	ifstream f("pscpld.in");
	ofstream g("pscpld.out");
	string str = ".";
	for(char ch; f >> ch; ){
		str.push_back(ch);
		str.push_back('.'); }

	vector<int> v(str.size());
	pscpld(str, v);
	int rez = 0;
	for(int i = 0; i < str.size(); ++i){
		rez += (v[i]+1)/2; }
	g << rez;
	return 0; }