Cod sursa(job #105539)

Utilizator MariusMarius Stroe Marius Data 17 noiembrie 2007 18:59:02
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.31 kb
#include <stdio.h>
#include <string.h>

const char iname[] = "abc2.in";
const char oname[] = "abc2.out";

#define MAXN  10000005

char T[MAXN];

struct hash_node {
	unsigned int hash;
	hash_node * next;
} *H[666013];


inline bool find(int r, unsigned int t)
{
	for (hash_node *p = H[r]; p; p = p -> next)
		if (p -> hash == t)
			return true;
	return false;
}

inline void insert(int r, unsigned int t)
{
	hash_node *p = new hash_node;
	p -> hash = t, p -> next = H[r], H[r] = p;
}

int main(void)
{
	FILE *fi = fopen(iname, "r");

	char word[22] = {0};
	int n;
	int m;

	int cnt = 0;
	
	fscanf(fi, "%s\n", T);
	n = (int)strlen(T);
	m = 0;
		
	while (fscanf(fi, "%s\n", word) == 1) {
		if (m == 0)  
			m = (int)strlen(word);
		unsigned int t = 0;
		for (int i = 0; word[i]; ++ i)
			t = t * 3 + (word[i] - 'a');
		int r = t % 666013;
        if (!find(r, t))
			insert(r, t);
	}
	fclose(fi);

	unsigned int pow3 = 1;
	for (int i = 1; i < m; ++ i)
		pow3 = pow3 * 3;

	unsigned int t = 0;
	for (int i = 0; i < m; ++ i)
		t = t * 3 + (T[i] - 'a');
	for (int i = 0; i <= n - m; ++ i) {
		if (find(t % 666013, t))
			cnt ++;
		t = 3 * (t - pow3 * (T[i] - 'a')) + (T[i + m] - 'a');
	}

	FILE *fo = fopen(oname, "w");

	fprintf(fo, "%d\n", cnt);
	fclose(fo);

	return 0;
}