Cod sursa(job #474847)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 5 august 2010 11:16:45
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>      
#include <cstring>      
#include <vector>     
  
using namespace std;      
     
#define file_in "abc2.in"      
#define file_out "abc2.out"     
  
#define Nmax 10000005      
#define Mod 666013      
     
int N;    
char ta[Nmax];      
int n;      
vector <unsigned int> h[Mod+25];      
int sol=0;      
     
void baga(unsigned int x)      
{      
    int k=x%Mod;      
    for(vector <unsigned int>::iterator it=h[k].begin(); it!=h[k].end(); ++it)      
        if (*it==x)      
            return;      
    h[k].push_back(x);      
}      
     
int cauta(unsigned int x)      
{      
    int k=x%Mod;      
    for(vector <unsigned int>::iterator it=h[k].begin(); it!=h[k].end(); ++it)      
        if (*it==x)      
            return 1;      
    return 0;      
}      
     
void citire()      
{      
    char s[25];   
    int i;   
	
	freopen(file_in,"r",stdin);      
    freopen(file_out,"w",stdout);   
       
    fgets(ta,nmax,stdin);      
    N=strlen(ta)-1;      
    fgets(s,25,stdin);      
    n=strlen(s)-1;      
    do
	{      
        unsigned int nr=0;      
        for (i=0;i<n;++i)      
            nr=nr*3+(s[i]-'a');      
        baga(nr);      
    }      
    while(fgets(s,25,stdin));      
}      
     
  
void solve()      
{      
    unsigned int nr=0,mod=1;      
       
    for(int i=0;i<n-1;++i)      
    {      
        nr=nr*3+(ta[i]-'a');      
        mod*=3;      
    }      
       
    for(int i=n-1;i<N;++i)      
    {      
        nr=(nr%mod)*3+(ta[i]-'a');      
        sol+=cauta(nr);      
    }
    printf("%d", sol);   	
}      
     

int main()      
{      
  
       
    citire();      
    solve();      
     
    fclose(stdin);   
    fclose(stdout);   
       
    return 0;      
}