Cod sursa(job #1593821)

Utilizator RaTonAndrei Raton RaTon Data 8 februarie 2016 21:53:12
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char s[2000001];
int p[2000001];
int main(){
	char ch;
	int n, i, id, mx;
	long long sum;
	s[0] = '$';
	s[1] = '#';
	i = 2;
	f.get(ch);
	while( f.eof() == 0 && ch != '\n' ){
		s[i++] = ch;
		s[i++] = '#';
		f.get(ch);
	}
	s[i] = '\0';
	n = i;
	sum = 0;
	id = mx = 0;
	for( i = 1; i < n; i++ ){
		if( i < mx )
			if( mx - i - p[2 * id - i] >= 0 )
				p[i] = p[2 * id - i];
			else
				p[i] = mx - i;
		else
			p[i] = 1;
		
		while( s[i + p[i]] == s[i-p[i]] )
			p[i]++;
		
		if( i + p[i] > mx ){
			id = i;
			mx = i + p[id];
		}
		sum += (p[i] / 2);
	}
	g << sum;
	return 0;
}