Cod sursa(job #105494)

Utilizator MariusMarius Stroe Marius Data 17 noiembrie 2007 18:43:31
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.32 kb
#include <cstdio>
#include <vector>

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> A[666013], B[65599];


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

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

	vector <i64>::iterator it;

	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');
		a = t % 666013;
		b = t % 65599;
		if (A[a].size() < B[b].size())
			A[a].push_back(t);
		else
			B[b].push_back(t);
	}
	fclose(fi);

	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) {
		a = t % 666013;
		b = t % 665599;
		for (it = A[a].begin(); it != A[a].end(); ++ it) if (*it == t) {
			cnt ++;
			break ;
		}
		if (it == A[a].end())
			for (it = B[b].begin(); it != B[b].end(); ++ it) if (*it == t) {
				cnt ++;
				break ;
			}
		
		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;
}