Cod sursa(job #923659)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 23 martie 2013 18:40:53
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<fstream>
#include<string.h>
#include<vector>

using namespace std;

#define max_l 26
#define max_n 10005
#define MAX_L 1000010

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

int i , p , u , n , Sol[max_n];
char A[MAX_L] , s[max_n];


struct ac{
	int nr;
	vector<int> L;
	ac *nd[max_l];
	ac *fail;
	ac(){
		nr = 0;
		fail = NULL;
		memset(nd , 0 , sizeof(nd));
	}
}*T , *q[max_n*102] , *nod , *nod1;

void insert(ac *T , char *s , int nr){
	if((*s) > 'z' || (*s) < 'a'){
		T->L.push_back(nr);
	}
	else{
		int urm = (*s) - 'a';
		if(0==T->nd[urm])
			T->nd[urm] = new ac;
		insert(T->nd[urm] , s+1 , nr);
	}
}

void read(){
	
	f>>A;
	
	f>>n;
	
	for(int i=1;i<=n;i++){
		f>>s;
		insert(T , s , i);
	}
	
}

void bfs(){
	
	p = 1 , u = 1;
	
	T->fail = T; q[1] = T;
	
	while(p <= u){
		
		nod = q[p];
		
		for(i = 0 ; i<max_l ; i++){
			if(nod->nd[i]!=0){
				nod1 = nod->fail;
				
				while(nod1 != T && nod1->nd[i] == NULL)
					nod1 = nod1->fail;
				
				if(nod1->nd[i]!=NULL && nod1->nd[i] != nod->nd[i]){
					nod1 = nod1->nd[i];
				}
				
				nod->nd[i]->fail = nod1;
				
				q[++u] = nod->nd[i];
			}
		}
		
		p++;
	}
	
}

void solve(){
	
	int lungime = strlen(A);
	int urm ;
	
	ac *p = T;
	
	for(int i=0;i<lungime;i++){
		urm = A[i] - 'a';
		
		while(p!=T && p->nd[urm] == NULL)
			p = p->fail;
		
		if(p->nd[urm] != NULL)
			p = p->nd[urm];
		
		p->nr++;
	}
	
	
	
}

void antibfs(){
	
	int j;
	
	for(int i=u;i>0;i--){
		nod = q[i];
		
		if(nod->fail != NULL)
			nod->fail->nr += nod->nr;
		
		for(j = 0 ; j < nod->L.size() ; j++){
			Sol[ nod->L[j] ] = nod->nr;
		}
	}
	
}

void print(){
	
	for(int i = 1 ; i <= n ; i++)
		g<<Sol[i]<<"\n";
	
}

int main(){
	
	T = new ac;
	
	read();
	
	bfs();
	
	solve();
	
	antibfs();
	
	print();
	
	return 0;
}