Cod sursa(job #344064)

Utilizator blasterzMircea Dima blasterz Data 28 august 2009 12:57:18
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 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;
	list *pi, *pj;
	nod()
	{
		fail = 0;
		for(int i = 0; i < 3; ++i) next[i] = 0;
		pi = pj = 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]];
	}
	
	list *p = new list(++numOfStrings);
	p->next = T->pi;
	T->pi = p;
	if(T->pj == 0) T->pj = T->pi;
	
}

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(T->pi == 0 && fail->pi)
			T->pi = fail->pi,
			T->pj = fail->pj;
		else
		if(T->pi && fail->pi)
			T->pj->next = fail->pi;
	}
	
}

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);
	}
}

void search(char a[], int n, bool sol[])
{
	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->pi) sol[i] = 1;
		
	}
	
}

char a[10000001];
bool sol[10000001];

int main()
{
	freopen("abc2.in","r",stdin);
	gets(a);
	
	char x[32];
	int len = 0;
	
	while(!feof(stdin))
	{
		gets(x);
		len = strlen(x);
		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, sol);
	
	int nsol = 0;
	
	for(int i = 0; i < len; ++i)
		if(sol[i]) ++nsol;
	
	freopen("abc2.out","w",stdout);
	printf("%d\n", nsol);
	return 0;
}