Cod sursa(job #100832)

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

char c, buf[22];
int L, Ans = 0;

int N = 0;
unsigned a[50005];

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

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

inline int hget(int x)
{
    int l = -1, r = N, m;
    while (l+1 < r)
    {
        m = (l+r)/2;
        if (x <= a[m])
            r = m;
        else
            l = m;
    }
    return a[r] == x ? 1 : 0;
}

int main(void)
{
	FILE *fi = fopen("abc2.in", "r");
    do c = fgetc(fi); while (c != '\n');
	while (fgets(buf, 22, fi))
        a[N++] = f(buf);
	fclose(fi);
    for (L = 0; LET(buf[L]); L++);
    sort(a, a+N);
    
	fi = fopen("abc2.in", "r");
	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;
}