Cod sursa(job #105435)

Utilizator MariusMarius Stroe Marius Data 17 noiembrie 2007 17:20:49
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.11 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

#define MAXN  10000005

typedef long long i64;

char T[MAXN];

vector <i64> V[666013];

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

	char word[22] = {0};
	int n;
	int m;
	int cnt = 0, k;
	i64 pow3 = 1;
	i64 t;

	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);
		t = 0;
		for (int i = 0; word[i]; ++ i)
			t = t * 3 + (word[i] - 'a');
		V[t % 666013].push_back(t);
	}
	fclose(fi);

	for (int i = 0; i < 666013; ++ i)
		sort(V[i].begin(), V[i].end());

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

	t = 0;
	for (int i = 0; i < m; ++ i)
		t = t * 3 + (T[i] - 'a');
	for (int i = 0; i < n - m; ++ i) {
		k = t % 666013;
		if (binary_search(V[k].begin(), V[k].end(), 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;
}