Cod sursa(job #106129)

Utilizator sims_glAlexandru Simion sims_gl Data 18 noiembrie 2007 13:22:56
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define nm 50010
#define lm 10000100
#define mod 666013

int n, sol;
char s[lm], a[nm][20];
vector<int> mat[666013];

int main()
{
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);
	
	fgets(s, 10000010, stdin);

	while(!feof(stdin))
		fgets(a[++n], 24, stdin);

	--n;

	for (int i = 1; i <= n; ++i) {
		int crt = 0, m = strlen(a[i]) - 1;

		for (int j = 0; j < m; ++j)
			crt = (crt * 3 + a[i][j] - 'a') % mod;

		mat[crt].push_back(i);
	}

	unsigned crt = 0;
	int k = strlen(a[1]) - 1;

	for (int i = 0; i < k - 1; ++i)
		crt = crt * 3 + s[i] - 'a';

	int sm = strlen(s) - 1, pow = 1;

	for (int i = 1; i < k; ++i)
		pow *= 3;

	for (int i = k - 1; i < sm; ++i) {
		crt = (unsigned)crt * 3 + s[i] - 'a';

		int aux = (unsigned)crt % mod, m = mat[aux].size();

		int ok = 0;

		for (int j = 0; j < m; ++j) {
			ok = 1;
			for (int l = 0; l < k; ++l)
				if (a[mat[aux][j]][l] != s[i - k + l + 1])
					ok = 0;
		}

		sol += ok;

		crt = crt - ((unsigned)s[i - k + 1] - 'a') * pow;
	}

	printf("%d\n", sol);

	return 0;
}