Cod sursa(job #2668421)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 4 noiembrie 2020 21:38:05
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.59 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

struct ahocor {
	int matches;
	vector<int> nd;
	ahocor *sons[26], *fail;
	ahocor() {
		matches = 0;
		fail = 0;
		memset(sons, 0,sizeof(sons));
	}
} *root, *q[1000003];

int q_len;

char a[1000003];
char current_word[10003];
int antibfs_res[103];


void insert_ahocor(ahocor *node, char * word, int wordno) {
	if (*word < 'a' || *word > 'z') {
		node->nd.push_back(wordno);
		return;
	}
	int current_son =*word - 'a';
	if(node->sons[current_son] == 0)
		node->sons[current_son] = new ahocor;
	insert_ahocor(node->sons[current_son], word+1, wordno);
}


void bfs(ahocor * start) {
	ahocor *current_fail, *current_node;
	start->fail = start;

	int q_front = 1;
	q_len = 1;
	q[1] = start;

	while (q_front <= q_len) {
		current_node = q[q_front];
		++q_front;

		for(int i=0; i<26; ++i)
			if (current_node->sons[i]) {
				for(current_fail = current_node->fail; current_fail != start && current_fail->sons[i] != NULL; current_fail = current_fail->fail);

				if (current_fail->sons[i] && current_fail->sons[i] != current_node->sons[i])
					current_fail = current_fail->sons[i];

				current_node->sons[i]->fail = current_fail;

				++q_len;
				q[q_len] = current_node->sons[i];
			}
	}
}


void match_a(int n) {
	ahocor * current_node = root;
	int current_son = 0;

	for(int i=0; i<n; ++i) {
		current_son = a[i] - 'a';

		for(;current_node->sons[current_son]==NULL && current_node != root; current_node = current_node->fail);

		if (current_node->sons[current_son])
			current_node = current_node->sons[current_son];
		current_node->matches++;
	}

}


void antibfs(ahocor * start) {
	ahocor * current_node;
	for(int i = q_len; i>=1; --i) {
		current_node = q[i];
		if (current_node->fail)
			current_node->fail->matches += current_node->matches;

		for(int j=0; j<current_node->nd.size(); ++j)
			antibfs_res[current_node->nd[j]] = current_node->matches;
	}

}


int main() {
	freopen("ahocorasick.in", "r", stdin);
	freopen("ahocorasick.out", "w", stdout);

	scanf("%s", a);
	int n = strlen(a), m, current_n;
	if(a[n-1] == '\n') {
		--n;
		a[n] = 0;
	}

	root = new ahocor;
	scanf("%d", &m);

	for(int i=1; i<=m; ++i) {
		scanf("%s", current_word);
		current_n = strlen(current_word);
		if (current_word[current_n] == '\n') {
			--current_n;
			current_word[current_n] = 0;
		}

		insert_ahocor(root, current_word, i);

	}

	bfs(root);
	match_a(n);
	antibfs(root);

	for(int i=1; i<=m; ++i)
		printf("%d\n", antibfs_res[i]);


	return 0;
}