Cod sursa(job #1226749)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 7 septembrie 2014 00:56:01
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <queue>
#define DIMM 1000001
#define DIM 10001

using namespace std;

ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

struct trie {
	int nr;
	trie *back, *fii[26];
	vector<trie*> v;
	trie() {
		back = NULL;
		nr = 0;
		for (int i = 0; i < 26; ++i)
			fii[i] = NULL;
	}
} *T = new trie;

trie *Res[101];

int n;

char A[DIMM], s[DIM];

trie *update(trie *nod, char *s) {
	if (*s == 0)
		return nod;
	if (nod->fii[*s - 'a'] == NULL)
		nod->fii[*s - 'a'] = new trie;
	return update(nod->fii[*s - 'a'], s + 1);
}

void BFS() {
	queue<trie*> Q;
	Q.push(T);
	while (!Q.empty()) {
		trie *nod = Q.front();
		Q.pop();
		for (int i = 0; i < 26; ++i)
		if (nod->fii[i] != NULL) {
			trie *aux = nod->back;
			while (aux && !aux->fii[i])
				aux = aux->back;
			if (!aux)
				aux = T;
			else
				aux = aux->fii[i];
			nod->fii[i]->back = aux;
			aux->v.push_back(nod->fii[i]);
			Q.push(nod->fii[i]);
		}
	}
}

void DFS(trie* nod) {
	for (vector<trie*>::iterator it = nod->v.begin(); it != nod->v.end(); ++it) {
		DFS(*it);
		nod->nr += (*it)->nr;
	}
}

int main() {
	f >> A;
	f >> n;
	for (int i = 1; i <= n; ++i) {
		f >> s;
		Res[i] = update(T, s);
	}

	BFS();
	trie *aux = T;
	for (char *p = A; *p; ++p) {
		while (aux && !aux->fii[*p - 'a'])
			aux = aux->back;
		if (!aux)
			aux = T;
		else
			aux = aux->fii[*p - 'a'];
		++aux->nr;
	}

	DFS(T);

	for (int i = 1; i <= n; ++i)
		g << Res[i]->nr << "\n";
	return 0;
}