Cod sursa(job #570766)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 3 aprilie 2011 16:13:20
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2000010

char x[Nmax];
char v[Nmax];
int l[Nmax];
int i,n;

int main()
{
	freopen("pscpld.in","r",stdin);
	freopen("pscpls.out","w",stdout);
	
	fgets(x,Nmax,stdin);
	
	n = 1;
	v[1] = '*';

	for (int i = 0; x[i] >= 'a' && x[i] <= 'z'; ++i) {
		v[++n] = x[i];
		v[++n] = '*';		
	}

	int st=1, dr=3;
	l[2] = 1;

	for (int i = 3; i <= n; ++i) {
		if (i<=dr) {
			int poz = dr-i;
			if (i + l[st+poz] >= dr) {
				l[i] = dr-i;
				st = i - l[i];
				dr = i + l[i];
				while (v[st-1] == v[dr+1] && st > 1) {
					--st;
					++dr;
					++l[i];      
				}                                  
			} 
				else    
			l[i] = l[st+poz];
		}    
		else{
			l[i] = 0;
			st = i;
			dr = i;
			while (v[st-1] == v[dr+1] && st > 1) {
				--st;
				++dr;
				++l[i];      
			}     
		}
	}

	int ans = 0;
	for (i=1; i<=n; ++i)
		ans += (l[i]+1)/2;
	
	printf("%d\n", ans);
	return 0;
}