Cod sursa(job #75206)

Utilizator thanhvyThanh Vy thanhvy Data 31 iulie 2007 11:43:32
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <cstring>

#define maxn (1 << 21)

char s[maxn];
int n, f[maxn], fi;

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

int main() {
	register int i, rec, p, tmp, p1, p2;
	long long ans;
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);
    gets(s); 
	n = strlen(s);
	p1 = (n << 1);
	p2 = n - 1;
	while (p1 >= 0) {
          if (p1 & 1) {
             s[p1] = s[p2];
             --p2;    
          }
          else 
               s[p1] = '.';
          --p1;
    }
    n <<= 1;
	ans = 0;
	for (rec = 0, p = -1, i = 0; i <= n; ++i){
		for (fi = (i <= p) ? min(f[(rec << 1) - i], p - i) : 0; ((p1 = i - fi - 1) >= 0) && ((p2 = i + fi + 1) <= n) && (s[p1] == s[p2]); ++fi);
		if ((tmp = i + fi) > rec){
			p = tmp;
			rec = i;
		}
		ans += (fi + 1) >> 1;
		f[i] = fi;
	}
	printf("%lld\n", ans);
	return 0;
}