Cod sursa(job #531018)

Utilizator Robert29FMI Tilica Robert Robert29 Data 8 februarie 2011 19:58:12
Problema Abc2 Scor 0
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;
long long w[50001];
char v[10000001],a[50001][20];
int main(){
	int i=1;
	fscanf(f,"%s",&v);
	int x1=strlen(v);
	fscanf(f,"%s",&a[i]);
	while(a[i][0])
		fscanf(f,"%s",&a[++i]);
	int x=strlen(a[1]);
	i--;
	for(int j=1;j<=i;j++){
		long long z=0;
		long long t=1;
		for(int k=0;k<x;k++){
			z+=(a[j][k]-'a')*t;
			t*=3;
		}
		w[j]=z;
	}
	sort(w+1,w+i+1);
	long long z=0;
	long long t=1;
	for(int j=0;j<x;j++){
		z+=(v[j]-'a')*t;
		t*=3;	
	}
	int nr=0;
	int p=1;
	int u=i;
	while(p<=u){
		int m=(p+u)/2;
		if(w[m]<z)
			p=m+1;
		else
			if(w[m]>z)
				u=m-1;
			else{
				nr++;
				break;
			}
	}
	int d=pow(3,x-1);		
	for(int j=x;j<x1;++j){
		z=z-(v[j-x]-'a');
		z/=3;
		z+=(v[j]-'a')*d;
		int p=1;
		int u=i;
		while(p<=u){
			int m=(p+u)/2;
			if(w[m]<z)
				p=m+1;
			else
				if(w[m]>z)
					u=m-1;
				else{
					nr++;
					break;
				}
		}
		
	}		
	fprintf(g,"%d",nr);
	
	fclose(g);
	fclose(f);
	return 0;
}