Cod sursa(job #75282)

Utilizator Ragnar_LodbrokGrosu Codrut Ragnar_Lodbrok Data 31 iulie 2007 21:10:11
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <cstring>

#define maxn (1 << 21)

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

typedef long LL;

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

int main() {
	int i, rec, p, p1, p2;
	LL ans;
	FILE *fin,*fout;
    fin=fopen("pscpld.in","r");
    fout=fopen("pscpld.out","w");
    fscanf(fin,"%s",s);
    fclose(fin); 
	n = strlen(s);
	p1 = (n << 1);
	p2 = n - 1;
	while (p1 >= 0) {
          if (p1 & 1) 
             s[p1--] = s[p2--];
          else 
               s[p1--] = '.';
    }
    n <<= 1;
	ans = 0;
	for (rec = 0, p = -1, i = 0; i <= n; ++i){
		if (i <= p) 
          {fi = f[(rec << 1) - i];
           if (fi > p - i) fi=p-i;
          }
        else fi=0;
        while (i - fi - 1>= 0&&i + fi + 1<= n&&s[i-fi-1] == s[i+fi+1]) ++fi;
		if (i + fi > p){ //>rec
			p = i+fi;
			rec = i;
		}
		ans += (fi + 1) >> 1;
		f[i] = fi;
	}
    fprintf(fout,"%lld\n", ans);
    fclose(fout);
	return 0;
}