Cod sursa(job #101304)

Utilizator andrei.12Andrei Parvu andrei.12 Data 13 noiembrie 2007 12:36:38
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.42 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char w[10000000], c, s[20],*pp;
int x, i, nr, ind, lg;
unsigned int sol, r, v[50005], pt[21], cnt;
int cmp(const void*a, const void*b){
	unsigned int x  = *(unsigned int *)a, y = *(unsigned int*)b;
	if (x < y) return -1;
	if (x > y) return 1;
	return 0;
}
int caut(unsigned int cnt){
	int li = 0, ls = ind, x;
	while (li <= ls){
		x = (li+ls) / 2;
		if (cnt == v[x])
			return 1;
		else
			if (cnt < v[x])
				ls = x-1;
			else
				li = x+1;
	}
	return 0;
}
int main()
{
	freopen("abc2.in", "rt", stdin);
	freopen("abc2.out", "wt", stdout);
	fgets(w, 10000005, stdin);
	pt[0] = 1;
	for (i=1; i<=20; i++)
		pt[i] = 3*pt[i-1];
	ind = -1;
	while (!feof(stdin)){
		fgets(s, 25, stdin);
		nr = strlen(s) - 1;
		r = 0;
		for (i=0; i<nr; i++){
			x = s[i]-'a';
			r += x*pt[nr-i-1];
		}
		v[++ind] = r;
	}
	qsort(v, ind+1, sizeof(v[0]), cmp);
	//lg = strlen(w);
	//lg --;
	cnt = 0;
	for (i=0; i<nr; i++){
	//for(pp=w;*pp!='\n';++p){
		x = w[i]-'a';
		//x=*pp-'a';
		cnt += pt[nr-i-1]*x;
	}
	if (caut(cnt)) 
		sol ++;
	//for (i=nr; i<lg; i++){
	for(pp=w+nr;*pp!='\n';++pp){
		//x = w[i]-'a';
		x=*pp-'a';
		//cnt = (cnt - pt[nr-1]*(w[i-nr]-'a')) * 3 + x;
		cnt = (cnt - pt[nr-1]*(*(pp-nr)-'a')) * 3 + x;
		/*
		if (caut(cnt))
			sol ++;
		*/
		sol+=caut(cnt);
	}
	printf("%u\n", sol);
	fclose(stdin);
	fclose(stdout);
	return 0;
}