Cod sursa(job #13337)

Utilizator gcosminGheorghe Cosmin gcosmin Data 6 februarie 2007 12:03:27
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

#define NMAX 1000010

int n;

char s[NMAX];

char a[NMAX << 1];
int lung[NMAX << 1];

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

int main()
{
	int i, q, lc, w;
	
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);

	scanf("%s", s);

	for (i = 0; s[i]; i++) {
		a[n++] = s[i];
		a[n++] = '$';
	}

	int last = -1, j = -1;

	long long rez = 0;

	for (i = 0; i < n; i++) {
		if (i > last) {
			for (q = 1; i + q < n && i - q >= 0 && a[i - q] == a[i + q]; q++);
			q--;

			lung[i] = q;
			last = i + q;
			j = i;
		} else {
			w = 2 * j - i;

			lc = MIN(lung[w], last - i);

			if (lc == last - i) {
				for (q = last - i + 1; i + q < n && i - q >= 0 && a[i - q] == a[i + q]; q++);
				q--;

				lc = q;

				last = i + q;
				j = i;
			}

			lung[i] = lc;
		}

		rez += (i & 1) ? (lung[i] + 1) / 2 : lung[i] / 2 + 1;
	}

/*	printf("%s\n", a);
	for (i = 0; i < n; i++) printf("%d ", lung[i]);
	printf("\n");
*/
	printf("%lld\n", rez);
	
fclose(stdin);
fclose(stdout);
return 0;
}