Cod sursa(job #942196)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 21 aprilie 2013 12:55:29
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#include <string.h>

int n, nr;
int v[2000005], sol[2000005];
char s[100005];

inline int min (int a, int b) {return a < b ? a : b;}

void pscpld ()
{
	int i, l = 1, r = 1, solf = 0;
	sol[1] = 1;
	for (i = 2; i <= nr; i ++)
	{
		sol[i] = 1;
		if (r > i)
			sol[i] = min (sol[l + r - i], r - i + 1);
		if (i + sol[i] - 1 >= r)
		{
			l = i - sol[i] + 1;
			r = i + sol[i] - 1;
			while (1 < l && r < nr && v[l - 1] == v[r + 1])
			{
				sol[i] ++;
				l --;
				r ++;
			}
		}
		solf += sol[i] / 2;
	}
	printf ("%d\n", solf);
}

int main ()
{
	freopen ("pscpld.in", "r", stdin);
	freopen ("pscpld.out", "w", stdout);
	
	gets (s + 1);
	n = strlen (s + 1);
	
	int i;
    for (i = 1; i <= n; i ++)
	{
		v[++ nr] = -1;
		v[++ nr] = s[i] - 'a';
	}
	v[++ nr] = -1;
	v[0] = -1000000000;
	v[nr + 1] = 1000000000;
	
	pscpld ();
	return 0;
}