Cod sursa(job #325916)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 iunie 2009 22:41:49
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <ctime>

using namespace std;

#define file_in "abc2.in"
#define file_out "abc2.out"

#define Nmax 10010001
#define Mmax 25
#define N_max 50100

#define Mod 666013

vector <int> h[Mod+Mmax];
char ta[Nmax];
char s[Mmax];
int nr,mod,n,N,sol;
//long long my_time;

int search(int x)   
{   
    int k,i;   
    k=x%Mod;   
           
    for(vector <int> :: iterator it=h[k].begin();it!=h[k].end();++it)      
         if (*it==x)   
              return 1;   
    return 0;   
}   
  
void add(int x)   
{   
    int i,k;   
    k=x%Mod;   
    

	if (search(x))
		 return ;
    h[k].push_back(x);   
}   


int main()
{
	//my_time=clock();
	int i;
	freopen(file_in,"r",stdin);
		
	fgets(ta,Nmax,stdin);
	N=strlen(ta)-1;
	fgets(s,Mmax,stdin);
	n=strlen(s)-1;

	do
	{
		nr=0;
		for (i=0;i<n;++i)
			 nr=nr*3+s[i]-'a';
		add(nr); 
    }
	while(fgets(s,Mmax,stdin));
	
	fclose(stdin);
	
	nr=sol=0;
	mod=1;
	for (i=0;i<n-1;++i)
	{
		nr=nr*3+ta[i]-'a';
		mod*=3;
	}
	//nr=0;
	for (i=n-1;i<N;++i)
	{
		nr=(nr%mod)*3+ta[i]-'a';
		if (search(nr))
			 sol++;
	}
	
	freopen(file_out,"w",stdout);
	
	printf("%d", sol);
	
	
	//printf ("Solution ended in %.4lf\n",(double)((double)clock()-my_time)/CLOCKS_PER_SEC);   
	fclose(stdout);
	
	return 0;
	
}