Cod sursa(job #100842)

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

#define HMAX 666013

vector<int> h[HMAX];
char c, buf[22];
char s[10000005];
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; LET(a[i]); 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;
}

int main(void)
{
    freopen("abc2.in", "r", stdin);
    gets(s);
    
	while (gets(buf))
   		hadd(f(buf));

    for (L = 0; LET(buf[L]); L++);

	unsigned r = 0, M = 1, T = strlen(s);
    int i;
    for (i = 0; i < L-1; i++) M *= 3;
    for (i = 0; i < T; i++)
	{
		if (i+1 < L)
			r = r*3+s[i]-'a';
		else
        {
            while (r >= M) r -= M;
			r = r*3+s[i]-'a';
            if (hget(r))
                ++Ans;
        }
    }

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