Cod sursa(job #2763812)

Utilizator DragosC1Dragos DragosC1 Data 16 iulie 2021 21:13:47
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <fstream>
#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[100000001];
 
int q_len;
 
char a[1000001];
char current_word[10001];
int antibfs_res[101];
 
 
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];
			}
	}
 
	start->fail = 0;
}
 
 
void match_a() {
	ahocor * current_node = root;
	int current_son = 0;
 
	for(int i=0; a[i]>='a'&&a[i] <='z'; ++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() {
	ifstream in("ahocorasick.in");
	ofstream out("ahocorasick.out");
 
	in >> a;
	int m;
 
	root = new ahocor;
	in >> m;
 
	for(int i=1; i<=m; ++i) {
		in >>current_word;
		insert_ahocor(root, current_word, i);
	}
 
	bfs(root);
	match_a();
	antibfs(root);
 
	for(int i=1; i<=m; ++i)
		out << antibfs_res[i] << '\n';
 
 
	return 0;
}