Cod sursa(job #100812)

Utilizator azotlichidAdrian Vladu azotlichid Data 12 noiembrie 2007 19:16:27
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.59 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define HMAX 666013

vector<int> h[HMAX];
char buf[22];
int L, Ans = 0;

#define LET(x) ('a' <= (x) && (x) <= 'c')

unsigned f(char a[])
{
	unsigned ret = 0;
    register int i, x = strlen(a);
	for (i = 0; i < x; i++)
		ret = ret*3+a[i]-'a';
	return ret;
}

inline void hadd(unsigned x)
{
	h[x%HMAX].push_back(x);
}

inline int hget(unsigned x)
{
	unsigned p = x%HMAX;
	for (vector<int> :: iterator it = h[p].begin(); it != h[p].end(); it++)
		if (*it == x)
			return 1;
	return 0;
}


void gen(void)
{
    int i, j;
    freopen("abc2.in", "w", stdout);
    for (i = 0; i < 10000000; i++)
        printf("%c", 'a'+rand()%3);
    printf("\n");

    for (i = 0; i < 50000; i++)
    {
        for (j = 0; j < 20; j++)
            printf("%c", 'a'+rand() % 3);
        printf("\n");
    }
}

int main(void)
{
//    gen(); return 0;
	FILE *fi = fopen("abc2.in", "r");
    do fscanf(fi, "%c", buf); while (*buf != '\n');
    
	while (fscanf(fi, "%s\n", buf) != EOF)
   		hadd(f(buf));
	fclose(fi);

	L = strlen(buf);

	fi = fopen("abc2.in", "r");
	char c;
	unsigned r = 0, M = 1;
    int i;
    
    for (i = 0; i < L-1; i++) M *= 3;
    i = 0;

	while (c = fgetc(fi), LET(c))
	{
		++i;
		if (i < L)
			r = r*3+c-'a';
		else
        {
            while (r >= M) r -= M;
			r = r*3+c-'a';
            if (hget(r))
                ++Ans;
        }
    }

	fclose(fi);
	fprintf(fopen("abc2.out", "w"), "%d\n", Ans);
	return 0;
}