Cod sursa(job #227932)

Utilizator ProtomanAndrei Purice Protoman Data 5 decembrie 2008 22:18:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>   
#include <algorithm>   
#include <string.h>   
#include <math.h>   
#define mx 10000010   
#define bz_hash 184371   
  
using namespace std;   
  
struct poz   
{   
    unsigned int el;   
    poz *ua;   
} *hash[bz_hash + 2];   
char s[mx + 2];   
char str[22];   
unsigned int v[4];   
long i, j, n, nm, h, nr;   
unsigned int x;   
  
void coh(long loc, unsigned int cant)   
{   
    poz *p = new poz;   
    p->el = cant;   
    p->ua = hash[loc];   
    hash[loc] = p;   
}   
  
int comp(int id, unsigned int x)   
{   
    for (poz *p = hash[id]; p; p = p->ua)   
        if (p->el == x)   
            return 1;   
    return 0;   
}   
  
int main()   
{   
    double A = (sqrt((double) 5) - 1) / 2;   
    freopen("abc2.in","r",stdin);   
    freopen("abc2.out","w",stdout);   
    fgets(s, mx + 4, stdin);   
    nm = strlen(s) - 1;   
    while (!feof(stdin))    
    {   
        fgets(str, 22, stdin);   
        h = strlen(str) - 1;   
        x = 0;   
        for (int i = 0; i < h; i++)   
            x = x * 3 + str[i] - 96;   
        double gs = A * x - (unsigned int) (x * A);   
        int loc = (double) gs * bz_hash;   
        if (!comp(loc, x))   
            coh(loc, x);   
    }   
    v[1] = 1;   
    for (int i = 0; i < h - 1; i++)   
        v[1] = v[1] * 3;   
    v[2] = v[1] * 2;   
    v[3] = v[1] * 3;   
    x = 0;   
    for (int i = 0; i < nm; i++)   
    {   
        if (i >= h)   
            x = x - v[s[i - h] - 96];   
        x = x * 3 + s[i] - 96;   
        double gs = A * x - (unsigned int) (x * A);   
        int loc = (double) gs * bz_hash;   
        if (i > h - 2)   
            nr += comp(loc, x);   
    }   
    printf("%ld", nr);   
    fclose(stdin);   
    fclose(stdout);   
    return 0;   
}