Cod sursa(job #103482)

Utilizator hellraizerChiperi Matei hellraizer Data 15 noiembrie 2007 13:23:11
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.43 kb
#include <stdio.h>
#include <stdlib.h>

#define L_MAX 10000001
#define M_MAX 50001

char v[L_MAX];
unsigned int a[M_MAX],b[M_MAX],k,ultim;
int L,m,n,s;
 
void merge_sort(int l, int r){
	int m = (l + r) >> 1, i, j, k;  
    if (l == r) return;  
    merge_sort(l, m);  
    merge_sort(m + 1, r);  
    for (i=l, j=m+1, k=l; i<=m || j<=r; )  
        if (j > r || (i <= m && a[i] < a[j]))  
            b[k++] = a[i++];  
        else  
            b[k++] = a[j++];  
    for (k = l; k <= r; k++) a[k] = b[k];  
}  

void bin_src(){
	int i, step;
	for (step=1;step<=m;step<<=1);
	for (i=0;step;step>>=1)
		if (i+step<=m && a[i+step]<=k)
			i+=step;
	if (a[i]==k)
		s++;
}

int main(){
	int i;
	char x;
	FILE *fin=fopen("abc2.in","r");
	L=0;
	fscanf(fin,"%c",&v[++L]);
	while (v[L]!='\n'){
		v[L]-='a';
		fscanf(fin,"%c",&v[++L]);
	}
	L--;
	n=0;m=0;
	fscanf(fin,"%c",&x);
	while (x!='\n'){
		n++;
		x-='a';
		a[m]=a[m]*3+x;
		fscanf(fin,"%c",&x);
	}
	if (!feof(fin))
		do{
			m++;
			for (i=1;i<=n;i++){
				fscanf(fin,"%c",&x);
				a[m]=a[m]*3+(x-'a');
			}
			fscanf(fin,"\n");
		}
		while (!feof(fin));
	fclose(fin);
	merge_sort(0,m);
	k=v[1];ultim=1;
	for (i=2;i<=n;i++){
		k*=3;
		k+=v[i];
		ultim*=3;
	}
	bin_src();
	for (i=n+1;i<=L;i++){
		k-=ultim*v[i-n];
		k*=3;
		k+=v[i];
		bin_src();
	}
	FILE *fout=fopen("abc2.out","w");
	fprintf(fout,"%d\n",s);
	fclose(fout);
	return 0;
}