Cod sursa(job #114319)

Utilizator goguGogu Marian gogu Data 13 decembrie 2007 19:38:45
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <bitset>
#define MOD 152457
#define pow(x) (1u<<(x))
#define f(x) (x%(1u<<20))
#define set(x) mask[f(x)]=1;
#define ok(x) (mask[f(x)])

using namespace std;

struct rec {
       int next, val; 
};

char text[10<<20];
unsigned lung, L;
unsigned aloc = MOD;
bitset<(1<<20)> mask;
rec h[2*MOD];

inline void baga(int x)
{
     unsigned key = x % MOD;
     set(x);
     while (h[key].next){
           if (h[key].val == x) return;
           key=h[key].next;
     }
     h[key].next = aloc++;
     h[key].val = x;
}

inline int exista(int x)
{
//    if (!ok(x)) return 0;
    unsigned key = x%MOD;
    while (h[key].next){
          if (h[key].val==x) return 1;
          key=h[key].next;
    }
    return 0;
}

inline unsigned lungime(char *s){
       unsigned k=0, x=0;
       while ('a'<=s[k] && s[k]<='c')
             x = 3*x + (s[k++]-'a');
       baga(x);
       return k;
}

int main()
{
    unsigned i;
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    fgets(text, 10<<22, stdin);
    char lin[30];
    fgets(lin, 30, stdin);
    lung = lungime(lin);
    while (lungime(lin)==lung)
          if (fgets(lin, 30, stdin)==NULL) break;
    unsigned nr, sol, pow=1;
    for (i=1; i<lung; i++)
        pow*=3;
    for (i=nr=0; i<lung; i++)
        nr=nr*3+(text[i]-'a');
    while ('a'<=text[L] && text[L]<='c') L++;
    for (i=lung, sol=exista(nr); i<L; i++){
        nr-=(text[i-lung]-'a')*pow;
        nr=3*nr+(text[i]-'a');
        sol += exista(nr);
    }
    printf("%d\n", sol);
}