Cod sursa(job #111612)

Utilizator peanutzAndrei Homorodean peanutz Data 1 decembrie 2007 14:41:15
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <bitset>

using namespace std;

#define Nmax 999997

#define MOD1 999997
#define MOD2 879993
#define MOD3 978331
#define MOD4 965413
#define MOD5 765413
#define MOD6 895413
#define MOD7 315413

bitset<Nmax> h1,h2,h3,h4,h5,h6,h7;
char a[10000100], tmp[23];
unsigned p[23], x, hash, cnt;
int k;

#define ins(x) h1[x%MOD1] = h2[x%MOD2] = h3[x%MOD3] = h4[x%MOD4] = h5[x%MOD5] = h6[x%MOD6] = h7[x%MOD7] = 1
#define is(x) h1[x%MOD1] && h2[x%MOD2] && h3[x%MOD3] && h4[x%MOD4] && h5[x%MOD5] && h6[x%MOD6] && h7[x%MOD7]

//3486784401

int calc()
{
    k = 0;
    for (int i=0;tmp[i] != '\n' && tmp[i] != 0;++i) ++k;        
    return k-1;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
           
    int x;
    p[0] = 1;
    for (int i=1;i<=20;++i) p[i] = p[i-1]*3;
    
    fgets(a,10000100,stdin);
    
    while(fgets(tmp,23,stdin))
    {
     if(k==0) k = calc();
     hash = 0;
     for (int i=k;i>=0;--i) hash += (tmp[i]-'a')*p[k-i];                               
     ins(hash); 
    }
    
    hash = 0;    
    for (int i=0;a[i]!='\n';++i)
    {
     if(i>k) hash -= (a[i-k-1]-'a')*p[k];
     hash = hash*3 + a[i]-'a';
     if (is(hash) && (i>=k)) ++cnt;      
      ++x;
    }
    
    printf("%d\n", cnt);   
        
    return 0;
}