Cod sursa(job #227915)

Utilizator ProtomanAndrei Purice Protoman Data 5 decembrie 2008 20:45:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#define mx 10000010
#define bz_hash 184371

using namespace std;

struct poz
{
    long long el;
    poz *ua;
} *hash[bz_hash + 2];
char s[mx + 2];
char str[22];
long long v[4];
long i, j, n, nm, h, nr;
long long x;

void coh(long loc, long long cant)
{
	poz *p = new poz;
	p->el = cant;
	p->ua = hash[loc];
	hash[loc] = p;
}

int comp(int id, long long x)
{
    for (poz *p = hash[id]; p; p = p->ua)
        if (p->el == x)
			return 1;
    return 0;
}

int main()
{
	long double A = (sqrt((long 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 - (long long) (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 - (long long) (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;
}