Cod sursa(job #344073)

Utilizator blasterzMircea Dima blasterz Data 28 august 2009 13:23:00
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
/*
* http://infoarena.ro/problema/abc2
* @author: Mircea Dima
* Aho Corasik O(n *L + m)
*/

#include <cstdio>
#include <queue>

using namespace std;

struct list
{
	int v;
	list *next;
	list(){ v = 0; next = 0;}
	list(int _v){v = _v; next = 0;}
};

struct nod
{
	nod *next[3];
	nod *fail;
	bool ok;
	nod()
	{
		fail = 0;
		for(int i = 0; i < 3; ++i) next[i] = 0;
		ok  = 0;
	}
};

nod *R = new nod();
int numOfStrings;

void insert(nod *T, char a[], int n)
{
	int i;
	for(i = 0; i < n; ++i)
	{
		if(T->next[a[i]] == 0)
			T->next[a[i]] = new nod();
		
		T = T->next[a[i]];
	}
	
	T->ok = 1;
}

inline void updateNode(nod *T, nod *father, int c)
{
	nod *p = father->fail;
	
	while(p && p->next[c] == 0) 
		p = p->fail;
	
	if(p == 0) T->fail = R;
	else T->fail = p->next[c];
	
	nod *fail = T->fail;

	if(T != fail)
	{
		if(fail->ok) T->ok = 1;
	}
	
}

void buildAutomata()
{
	queue<nod*> Q;
	int i;
	nod *T = R;
	
	for(i = 0; i < 3; ++i)
		if(T->next[i])
			Q.push(T->next[i]), 
			T->next[i]->fail = R;
			
	while(!Q.empty())
	{
		T = Q.front();
		Q.pop();
		
		for(i = 0; i < 3; ++i)
			if(T->next[i])
				Q.push(T->next[i]),
				updateNode(T->next[i], T, i);
	}
}

int nrSol;
int Len;
void search(char a[], int n)
{
	int i;
	nod *T = R;
	for(i = 0; i < n; ++i)
	{
		while(T && T->next[a[i]] == 0) T = T->fail;
		
		if(T == 0) { T = R;continue; }
		
		T = T->next[a[i]];
		
		if(T->ok) ++nrSol;
		
	}
	
}

char a[10000001];

int main()
{
	freopen("abc2.in","r",stdin);
	gets(a);
	
	char x[32];
	int len = 0;
	
	while(!feof(stdin))
	{
		gets(x);
		len = strlen(x);
		Len = len;
		for(int i = len -1; i >= 0; --i)
			x[i] -= 'a';
		insert(R, x, len);
	}
	
	buildAutomata();
	
	len = strlen(a);
	for(int i = 0; i < len; ++i)
		a[i] -= 'a';
	
	search(a, len);
	

	freopen("abc2.out","w",stdout);
	printf("%d\n", nrSol);
	return 0;
}