Cod sursa(job #75188)

Utilizator thanhvyThanh Vy thanhvy Data 31 iulie 2007 06:24:44
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <cstring>

#define maxn 1000001

static char s[maxn << 1], c;
static int n, f[maxn << 1];

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

int main() {
	register int i, j, rec, p, tmp, p1, p2, ans;
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);
	memset(s, '.', sizeof(s));
	n = -1;
	while (scanf("%c", &c) == 1 && c != '\n') {
          n += 2;
          s[n] = c;
    }
    ++n;
	ans = 0;
	for (rec = 0, p = -1, i = 0; i <= n; ++i){
		for (f[i] = (i <= p) ? min(f[(rec << 1) - i], p - i) : 0; ((p1 = i - f[i] - 1) >= 0) && ((p2 = i + f[i] + 1) <= n) && (s[p1] == s[p2]); ++f[i]);
		if ((tmp = i + f[i]) > rec){
			p = tmp;
			rec = i;
		}
		ans += (f[i] + 1) >> 1;
	}
	printf("%d\n", ans);
	return 0;
}