Cod sursa(job #582377)

Utilizator savimSerban Andrei Stan savim Data 15 aprilie 2011 11:57:57
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define MAX_N 2000010

int n;

long long  sol;

int d[MAX_N];

char s[MAX_N / 2], A[MAX_N];

int main() {

	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);

	scanf("%s", s);

	int L = strlen(s);
	for (int i = 0; i < L; i++) {
    	A[++n] = s[i];
		if (i != L - 1)
			A[++n] = '@';
	}	

	for (int i = 1; i <= n; i++) {
		if (i == 1)
			d[i] = 1;
		else
			d[i] = min(d[i - 2], d[i - 1] - 1);

		int left = i - d[i], right = i + d[i];
		while (0 < left && right <= n && A[left] == A[right]) {
        	d[i]++;
			left--;
			right++;
		}

		if (A[i] == '@')
			sol += d[i] / 2;
		else
			sol += (d[i] + 1) / 2;
	}

	printf("%lld\n", sol);

	return 0;
}