Cod sursa(job #1963656)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 12 aprilie 2017 17:58:25
Problema Aho-Corasick Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <cstdio>
#include <queue>
#include <cstring>
#include <unordered_set>

using namespace std;

struct Nod
{
	Nod *fail;
	Nod *vecini[26];
	unordered_set<int> indici;

	Nod()
	{
		fail = NULL;

		for(int i = 0; i < 26; i++)
		{
			vecini[i] = NULL;
		}
	}
};

Nod *root;

const int N = 105;

char sir[1000005];
int n;
char dictionar[N][10005];
int nrAparitii[N];

void addCuvant(char x[], int nr)
{
	Nod *a = root;	

	int l = strlen(x);

	for(int i = 0; i < l; i++)
	{
		char ch = x[i] - 'a';

		if(a->vecini[ch] == NULL)
		{
			a->vecini[ch] = new Nod();
			a = a->vecini[ch];
		}
		else
		{
			a = a->vecini[ch];
		}
	}

	a->indici.insert(nr);
}

void citire()
{
	scanf("%s\n", &sir);

	scanf("%d", &n);

	for(int i = 0; i < n; i++)
	{
		scanf("%s\n", &dictionar[i]);
	}
}

void construireTrie()
{
	for(int i = 0; i < n; i++)	
	{
		addCuvant(dictionar[i], i);
	}
}

void pregatireAhoCorasick()
{
	queue<Nod*> Q;

	int l = 26;

	for(int i = 0; i < l; i++)
	{
		if(root->vecini[i] != NULL)
		{
			Q.push(root->vecini[i]);
			root->vecini[i]->fail = root;
		}
	}

	while(Q.empty() == false)	
	{
		Nod *r = Q.front();
		Q.pop();
	
		for(int i = 0; i < 26; i++)	
		{
			if(r->vecini[i] != NULL)
			{
				Nod *u = r->vecini[i];
				Nod *v = r->fail;

				Q.push(u);

				while(v->vecini[i] == NULL && v != root)
				{
					v = v->fail;
				}

				if(v->vecini[i] == NULL)
				{
					u->fail = root;
				}
				else
				{
					u->fail = v->vecini[i];
				}

				for(auto y : u->fail->indici)
				{
					u->indici.insert(y);
				}
			}
		}
	}
}

void ahoCorasick()
{
	int l = strlen(sir);
	Nod *q = root;

	for(int i = 0; i < l; i++)
	{
		char ch = sir[i] - 'a';
		
		while(q->vecini[ch] == NULL && q != root)
		{
			q = q->fail;
		}

		q = q->vecini[ch];

		for(auto x : q->indici)
		{
			nrAparitii[x]++;
		}
	}
}

void afisare()
{
	for(int i = 0; i < n; i++)
	{
		printf("%d\n", nrAparitii[i]);
	}
}

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

	root = new Nod();
	citire();
	construireTrie();
	pregatireAhoCorasick();
	ahoCorasick();
	afisare();

	return 0;
}