Cod sursa(job #1117487)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 23 februarie 2014 16:17:58
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
#include <cstring>
#include <string>
#define NMAX 1000005
#define LMAX 10005
#define HMAX 26
#define TMAX 1200005
#define KMAX 105
#define ll long long
using namespace std;
char A[NMAX], B[LMAX], words[KMAX][LMAX];
int n, r;

struct trie
{
	ll res;
	trie *children[HMAX], *fail;
	
	trie()
	{
		res = 0;
		memset(children, 0, sizeof(children));
		fail = 0;
	}
};
trie *T = new trie();
trie *Q[TMAX];

void insert(trie *node, char *s)
{
	if (*s == '\n')
		return ;
		
	if (node -> children[*s - 'a'] == 0)
		node -> children[*s - 'a'] = new trie();
	
	insert(node -> children[*s - 'a'], s + 1);
}

void make_links()
{
	Q[r = 1] = T;
	for (int i = 1; i <= r; i++)
		for (int j = 0; j < HMAX; j++)
			if (Q[i] -> children[j])
			{
				Q[++r] = Q[i] -> children[j];
				if (Q[i] != T)
				{
					trie *aux = Q[i] -> fail;
					while (aux != T && aux -> children[j] == 0)
						aux = aux -> fail;
					if (aux -> children[j]) aux = aux -> children[j];
					Q[r] -> fail = aux;
				}
				else
					Q[r] -> fail = T;
			}
}

void go(trie *node, char *s)
{
	if (*s == '\n')
		return ;
		
	while (node != T && node -> children[*s -'a'] == 0)
		node = node -> fail;
	if (node -> children[*s - 'a']) node = node -> children[*s - 'a'];
	node -> res++;
	
	go(node, s + 1);
}

void update()
{
	Q[r = 1] = T;
	for (int i = 1; i <= r; i++)
		for (int j = 0; j < HMAX; j++)
			if (Q[i] -> children[j])
				Q[++r] = Q[i] -> children[j];
				
	for (int i = r; i > 1; i--)
		Q[i] -> fail -> res += Q[i] -> res;
}

ll get_res(trie *node, char *s)
{
	if (*s == '\n')
		return node -> res;
	return get_res(node -> children[*s - 'a'], s + 1);
}

int main()
{
	freopen("ahocorasick.in", "r", stdin);
	freopen("ahocorasick.out", "w", stdout);
	fgets(A + 1, NMAX, stdin);
	scanf("%d\n", &n);
	for (int i = 1; i <= n; i++)
	{
		fgets(B + 1, LMAX, stdin);
		insert(T, B + 1);
		memcpy(words[i], B, sizeof(B));
	}
	make_links();
	go(T, A + 1);
	update();
	for (int i = 1; i <= n; i++)
		printf("%lld\n", get_res(T, words[i] + 1));
	return 0;
}