Cod sursa(job #325905)

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

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[N_max];
char ta[Nmax];
char s[Mmax];
int nr,mod,n,N,sol=0;;

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()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	fgets(ta,Nmax,stdin);
	N=strlen(ta);
	fgets(s,Mmax,stdin);
	n=strlen(s);
	
	N--;
	n--;
	do
	{
		nr=0;
		for (i=0;i<n;++i)
			 nr=nr*3+s[i]-'a';
		add(nr); 
    }
	while(fgets(s,Mmax,stdin));
	
	nr=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++;
	}
	
	printf("%d", sol);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}