Cod sursa(job #1426623)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 30 aprilie 2015 01:15:51
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

int gaseste_nr_palindroame(const string& str){
	class Container{
		const string& str;
	public:
		constexpr Container(const string& s):
			str(s){}
		constexpr char operator[](const int x)const{
			return (x&1) ? str[x/2] : '#'; } } v(str);

	const int n = 2*str.size()+1;
	int rez = str.size();
	vector<int> marime_palind(n, 0);
	int citit_pana_la = -1;
	for(int i = 0; i < n; ++i){
		citit_pana_la = max(i, citit_pana_la);
		if(i+marime_palind[i] >= citit_pana_la){
			int j = citit_pana_la-i;
			while(i-j >= 0 && i+j < n && v[i-j] == v[i+j]){
				marime_palind[i+j] = marime_palind[i-j];
				citit_pana_la = max(citit_pana_la, i+j);
				++j; }
			marime_palind[i] = j-1; }
		rez += marime_palind[i]/2; }
	return rez; }
	 

int main(){
	ifstream f("pscpld.in");
	ofstream g("pscpld.out");
	string str;
	f >> str;
	g << gaseste_nr_palindroame(str);
	return 0; }