Cod sursa(job #534245)

Utilizator Robert29FMI Tilica Robert Robert29 Data 15 februarie 2011 15:20:09
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");
using namespace std;
unsigned int w[50001];
char v[10000001],a[21];
int N,tstep;
int cautbin(unsigned int val){
	
	int i, step;
	step=tstep;
    for (i = 1; step; step >>= 1)
        if (i + step <= N && w[i + step] <= val)
           i += step;
    return w[i] == val ;
}
int main(){
	int i=0;
	fscanf(f,"%s",v);
	int x1=strlen(v);
	fscanf(f,"%s",a);
	unsigned int z=0;
	unsigned int t=1;
	int x=strlen(a);
	do
	{
		++i;
		z=0;
		t=1;
		for(int k=0;k<x;++k){
			z+=(a[k]-'a')*t;
			t*=3;
		}
		w[i]=z;
	}while(fscanf(f,"%s",a)!=EOF);
	

	N=i;
	
	for(int j=1;j<=i;++j){
	
	}
	sort(w+1,w+i+1);
	tstep=1;
	for (tstep = 1; tstep <= N; tstep <<= 1);
	z=0;
	t=1;
	for(int j=0;j<x;++j){
		z+=(v[j]-'a')*t;
		t*=3;	
	}
	int nr=0;
	if(cautbin(z))
		nr++;
	int d=pow(3,x-1);		
	for(register int j=x;j<x1;++j){
		z=z-(v[j-x]-'a');
		z/=3;
		z+=(v[j]-'a')*d;
		
		N=i;
		if(cautbin(z))
			nr++;
		
	}		
	fprintf(g,"%d",nr);
	
	fclose(g);
	fclose(f);
	return 0;
}