Cod sursa(job #2790402)

Utilizator Rares31100Popa Rares Rares31100 Data 28 octombrie 2021 21:37:52
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.72 kb
#include <bits/stdc++.h>
using namespace std;

class AC_automaton
{
private:
	int sizeAlf;
	int (*Hash)(char);

	struct nod
	{
		vector <int> apar;
		nod **alf, *fail;
	};
	nod *origin;

	vector <int> Union (vector <int>& a, vector <int>& b)
	{
		vector <int> c;
		int st = 0, dr = 0;
		while(st < a.size() && dr < b.size())
			if(a[st] <= b[dr])
				c.push_back(a[st++]);
			else
				c.push_back(b[dr++]);

		while(st < a.size())
			c.push_back(a[st++]);

		while(dr < b.size())
			c.push_back(b[dr++]);

		return c;
	}
	void inserare(string& cuv, int index)
	{
		nod* poz = origin;

		for (auto lit : cuv)
		{
			int nr = Hash(lit);
			if (poz->alf[nr] == NULL)
			{
				nod* newRam = new nod();
				newRam->alf = new nod * [sizeAlf]();
				poz->alf[nr] = newRam;
			}

			poz = poz->alf[nr];
		}

		poz->apar.push_back(index);
	}
	void bfs()
	{
		queue <nod*> q;
		origin -> fail = origin;
		for(int i = 0; i < sizeAlf; i++)
			if(origin -> alf[i] != NULL)
			{
				origin -> alf[i] -> fail = origin;
				q.push(origin -> alf[i]);
			}

		while(!q.empty())
		{
			nod* curent = q.front();
			q.pop();

			for(int i = 0; i < sizeAlf; i++)
				if(curent -> alf[i] != NULL)
				{
					nod* findNod = curent;
					while(findNod != origin && findNod -> fail -> alf[i] == NULL)
						findNod = findNod -> fail;

					if(findNod -> fail -> alf[i] != NULL)
						curent -> alf[i] -> fail = findNod -> fail -> alf[i];
					else
						curent -> alf[i] -> fail = origin;

					curent -> alf[i] -> apar = Union(curent -> alf[i] -> apar, curent -> alf[i] -> fail -> apar);
					q.push(curent -> alf[i]);
				}
		}
	}
public:
	AC_automaton(string cuv[], int numarCuv, int sizeAlfabet, int (*HashFunction)(char))
	{
		sizeAlf = sizeAlfabet;
		Hash = HashFunction;

		origin = new nod();
		origin->alf = new nod*[sizeAlf]();

		for(int i = 1; i <= numarCuv; i++)
			inserare(cuv[i], i);

		bfs();
	}
	void sendAparitii(string &sir, int numarApar[])
	{
		nod* poz = origin;
		for(int i = 0; i < sir.size(); i++)
		{
			while(poz != origin && poz -> alf[Hash(sir[i])] == NULL)
				poz = poz -> fail;

			if(poz -> alf[Hash(sir[i])] != NULL)
				poz = poz -> alf[Hash(sir[i])];
			
			for(auto index : poz->apar)
				numarApar[index]++;
		}
	}
};

int n, numarApar[101];
string sir, cuv[101];
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

int Hash(char litera)
{
	return litera - 'a';
}

int main()
{
	ios::sync_with_stdio(false);
	fin >> sir >> n;

	for(int i = 1; i <= n; i++)
		fin >> cuv[i];

	AC_automaton ac(cuv, n, 26, Hash);
	ac.sendAparitii(sir, numarApar);

	for(int i = 1; i <= n; i++)
		fout << numarApar[i] << '\n';

	return 0;
}