Cod sursa(job #325930)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 iunie 2009 23:49:35
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 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 add(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 search(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;   
       
    fgets(ta,Nmax,stdin);      
    //gets(ta);   
    N=strlen(ta)-1;      
    fgets(s,25,stdin);      
    n=strlen(s)-1;      
       
    //while(!feof(stdin))      
    do
	{      
        //fgets(s,25,stdin);   
        //gets(s);   
        //n=strlen(s)-1;   
        unsigned int nr=0;      
        for (i=0;i<n;++i)      
            nr=nr*3+(s[i]-'a');      
        add(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+=search(nr);      
    }      
}      
     
void afisare()   
{   
    printf("%d", sol);   
}   
  
int main()      
{      
    freopen(file_in,"r",stdin);      
    freopen(file_out,"w",stdout);      
       
    citire();      
    solve();      
    afisare();   
  
    fclose(stdin);   
    fclose(stdout);   
       
    return 0;      
}