Cod sursa(job #2685917)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 18 decembrie 2020 00:25:32
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

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


struct TrieNode
{
	TrieNode *next[26];
	TrieNode *suf;
	int fv;
	TrieNode()
	{
		this->fv=0;
		this->suf=NULL;
		memset(this->next,NULL,sizeof(this->next));
	}
};

TrieNode *root = new TrieNode();
TrieNode* ans[1000005];

void insert(TrieNode *node,string &str,const int index,int i,const int len)
{
	if(i==len)
	{
		ans[index]=node;
		return;
	}
	int aux=str[i]-'a';
	if(node->next[aux]==nullptr)
		node->next[aux]=new TrieNode();

	insert(node->next[aux],str,index,i+1,len);
//	cout<<"INSERTDONE"<<"\n";
}

vector<TrieNode*> fin;
void linksss()
{
	//	cout<<"Entering the while...";
	queue <TrieNode*> q;
	q.push(root);
	while(!q.empty())
	{
		TrieNode *nod=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(nod->next[i]!=nullptr)
			{
				TrieNode *current;
				TrieNode *sufix;
				current=nod->next[i];
				sufix=nod->suf;
				fin.push_back(current);
				while(sufix!=root && sufix->next[i]==nullptr)
					sufix=sufix->suf;
				if(sufix->next[i]!=nullptr && sufix->next[i]!=current)
					current->suf=sufix->next[i];
				else
					current->suf=root;
				
				q.push(current);
			}
		}
	}
//	cout<<"Linking done!!"<<"\n";
}


int main()
{
	string s;
	in>>s;
	int n;
	in>>n;
	root->suf=root;
	for(int i=1;i<=n;i++)
	{
		string ss;
		in>>ss;
		int lung=ss.length();
		insert(root,ss,i,0,lung);
	}
	linksss();
	TrieNode *aux = root;
	for(auto ch:s)
	{
		int next_ch=ch-'a';
		while(aux!=root && aux->next[next_ch]==nullptr)
			aux=aux->suf;
		if(aux->next[next_ch]!=nullptr)
		{
			aux=aux->next[next_ch];
			aux->fv ++;
		}
	}
	for(int i=fin.size()-1;i>=0;i--)
		fin[i]-> suf-> fv+=fin[i]-> fv;

	for(int i=1;i<=n;i++)
		out<<ans[i]->fv<<"\n";
	return 0;
}