Cod sursa(job #2281642)

Utilizator shantih1Alex S Hill shantih1 Data 12 noiembrie 2018 16:47:38
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

int n,i,j;
int v[105],w[105];
char p[10005];
string S,nu;

struct trie
{
	int id,ap,n0;
	trie *fii[26],*bk;
	trie()
	{
		id=ap=n0=0;
		bk=0;
		memset(fii, 0, sizeof(fii));
	}
} *u,*r,*x;
trie *T=new trie;
deque<trie *> q,b;

void do_trie(trie *t,char *ch)
{
	if(*ch=='\0')
	{
		if(t->id==0)	t->id=i;
		w[i]=t->id;
		t->ap=1;
		return;
	}
	int nh=*ch-'a';
	if(t->fii[nh]==0)	t->fii[nh]=new trie;
	do_trie(t->fii[nh], ch+1);
}

void automata()
{
	for(int i=0;i<=25;i++)
		if(T->fii[i]!=0)
		{
			T->fii[i]->bk = T;
			q.push_back(T->fii[i]);
		}
	T->bk=T;
	while(!q.empty())
	{
		r=q.front();
		b.push_back(r);
		q.pop_front();
		for(int i=0;i<=25;i++)
			if(r->fii[i]!=0)
			{
				u=r->fii[i];
				x=r->bk;
				while(x!=T && x->fii[i]==0)
					x=x->bk;
				
				if(x->fii[i]!=0)	u->bk=x->fii[i];
				else	u->bk=T;
				q.push_back(u);
			}
	}
}
void strmatch()
{
	x=T;
	int ls=(int)S.size();
	for(int i=1;i<ls;i++)
	{
		int ch=S[i]-'a';
		while(x!=T && x->fii[ch]==0)
			x=x->bk;
		
		if(x->fii[ch]!=0)	x=x->fii[ch];
		x->n0++;
	}
}

int main() {
	
	getline(fin,nu);
	S=" "+nu;
	fin>>n;	getline(fin,nu);
	
	for(i=1;i<=n;i++)
	{
		fin.getline(p,10005,'\n');
		do_trie(T, p);
	}
	automata();
	strmatch();
	
	while(!b.empty())
	{
		x=b.back();
		b.pop_back();
		x->bk->n0+=x->n0;
		if(v[x->id]==0)	v[x->id]=x->n0;
	}
	
	for(i=1;i<=n;i++)
		fout<<v[w[i]]<<"\n";
}