Cod sursa(job #1844432)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 9 ianuarie 2017 23:30:53
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>

#define sigma 26
#define PLen 10001
#define SLen 1000001
#define NWMax 101

using namespace std;

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

int n, answ[NWMax], idx;
char input[SLen], pattern[NWMax][PLen];
bool mark[NWMax];

struct LinkedListElem {
	int word;
	LinkedListElem* next;

	LinkedListElem(int _word) {
		word = _word;
		next = NULL;
	}
};

struct Node {
	Node* go[sigma];
	Node* fail;
	LinkedListElem* firstWord;
	LinkedListElem* crtWord;
	int count;
	int label;

	Node(int _idx) {
		memset(go, 0, sizeof go);
		fail = NULL;
		firstWord = NULL;
		crtWord = NULL;
		label = _idx;
		count = 0;
	}
};

queue<Node*> QU;
Node* root;

void insert(Node* node, char* crtChar, int patCnt)
{
	if (*crtChar == '\0') {
		if (node->firstWord == NULL) {
			node->firstWord = new LinkedListElem(patCnt);
			node->crtWord = node->firstWord;
		}
		else {
			node->crtWord->next = new LinkedListElem(patCnt);
			node->crtWord = node->crtWord->next;
		}

		return;
	}

	char next = *crtChar - 'a';
	if (node->go[next] == NULL)
		node->go[next] = new Node(++idx);
	insert(node->go[next], crtChar + 1, patCnt);
}

void compute_fail()
{
	QU.push(root);
	while (!QU.empty()) {
		Node* crtNode = QU.front();
		QU.pop();

		for (int crtChar = 0; crtChar < sigma; crtChar++) {
			Node* son = crtNode->go[crtChar];
			if (son != NULL) {
				QU.push(son);

				Node* tmp = crtNode->fail;
				while (tmp != NULL && tmp->go[crtChar] == NULL)
					tmp = tmp->fail;

				if (tmp == NULL)
					son->fail = root;
				else {
					son->fail = tmp->go[crtChar];

					if (son->firstWord != NULL)
						son->crtWord->next = tmp->go[crtChar]->firstWord;
					else {
						son->firstWord = tmp->go[crtChar]->firstWord;
						son->crtWord = tmp->go[crtChar]->crtWord;
					}
				}
			}
		}
	}
}

void DFS(Node* node)
{
	mark[node->label] = true;

	for (LinkedListElem* crt = node->firstWord; crt != NULL; crt = crt->next)
		answ[crt->word] += node->count;

	for (int c = 0; c < 26; c++)
		if (node->go[c] != NULL)
			DFS(node->go[c]);
}

int main()
{
	f >> input;
	
	root = new Node(++idx);
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> pattern[i];
		insert(root, pattern[i], i);
	}

	compute_fail();

	int len = strlen(input);
	Node* tmp = root;
	for (int pos = 0; pos < len; pos++) {
		while (tmp != NULL && tmp->go[input[pos] - 'a'] == NULL)
			tmp = tmp->fail;

		if (tmp == NULL)
			tmp = root;
		tmp = tmp->go[input[pos] - 'a'];

		if (tmp != NULL)
			tmp->count++;
	}

	DFS(root);

	for (int i = 1; i <= n; i++)
		g << answ[i] << "\n";

	return 0;
}