Cod sursa(job #1726767)

Utilizator ArkinyStoica Alex Arkiny Data 8 iulie 2016 23:40:49
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include<fstream>
#include<string.h>
#include<queue>
using namespace std;

struct Node
{
	Node* c[27];
	vector<int> nr;
	int sm;
	Node  *fail;
}*Trie;

int f[110];

char s[1000010];
char a[10010];

queue<Node*> Q;
vector<Node*> vec;
void init()
{
	Trie = new Node;
	memset(Trie, 0, sizeof(Node));
}

void add_to_trie(int nr,const char *s)
{
	Node *node = Trie;

	for (int i = 0;s[i] != '\0';++i)
	{
		if (node->c[s[i] - 'a'])
			node = node->c[s[i] - 'a'];
		else
		{
			node->c[s[i] - 'a'] = new Node;
			memset(node->c[s[i] - 'a'], 0, sizeof(Node));
			node = node->c[s[i] - 'a'];
		}
	}
	node->nr.push_back(nr);
}

void create_fail_links()
{
	Q.push(Trie);

	while (Q.size())
	{
		Node *node = Q.front();
		vec.push_back(node);
		for (int i = 0;i < 27;++i)
		{
			if (!node->c[i])
				continue;
			Node *fail = node->fail;
			while (fail)
			{
				if (fail->c[i])
				{
					node->c[i]->fail = fail->c[i];
					break;
				}
				fail = fail->fail;
			}

			if (!fail && Trie->c[i] && Trie->c[i]!=node->c[i])
				node->c[i]->fail = Trie->c[i];
			else if(!fail)
				node->c[i]->fail = Trie;
			Q.push(node->c[i]);
		}
		Q.pop();
	}
}

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

int main()
{

	in >> s;

	int N;
	in >> N;
	init();
	for (int i = 1;i <= N;++i)
	{
		in >> a;
		add_to_trie(i,a);
	}
	create_fail_links();
	Node *node = Trie;
	for (int i = 0;s[i] != '\0';++i)
	{
		while (node != Trie && !node->c[s[i] - 'a'])
			node = node->fail;

		if (node->c[s[i] - 'a'])
			node = node->c[s[i] - 'a'];

		node->sm += 1;
	}
	
	for (int i = vec.size() - 1;i >= 0;--i)
	{
		for (int j = 0;j < vec[i]->nr.size();++j)
			f[vec[i]->nr[j]] = vec[i]->sm;

		if(vec[i]->fail)
			vec[i]->fail->sm += vec[i]->sm;
	}

	for (int i = 1;i <= N;++i)
		out << f[i] << '\n';

	return 0;
}