Cod sursa(job #120210)

Utilizator lemneLemne Lemne lemne Data 4 ianuarie 2008 16:44:11
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <cstring>
#include <cstdio>
#include <queue>

#define Tdim 10000001
#define Pdim 21
#define NumS 700001

using namespace std;

char T[Tdim];
char P[Pdim];

int Trie[NumS][3];
int Autm[NumS][3];

int Acc[NumS];

int NS;
int SOL;

struct elem
{
	int t;
	int muc;
	int nod;
};

queue <elem> Q;

void baga_trie()
{
	int st = 0;
	int i, n, muc;
	
	for(n=strlen(P), i=0; i<n; ++i)
	{
		muc = (int) P[i] - 'a';
		
		if(Trie[st][muc])
			st = Trie[st][muc];
			
		else
		{
			Trie[st][muc] = ++ NS;
			st = NS;
		}
	}
	
	Acc[st] = 1;
}

void baga_atm(int t, int muc, int nod)
{
	int b, i;
	
	b = Autm[t][muc];
	Autm[t][muc] = Trie[t][muc];
	
	if(Acc[b]) Acc[nod] = 1;
	
	for(i=0; i<3; ++i)
		if(Trie[b][i]) Autm[nod][i] = Trie[b][i];
		else Autm[nod][i] = Autm[b][i];
}

void bf()
{
	int i;
	
	elem e, new_e;
	
	for(i=0; i<3; ++i)
		if(Trie[0][i])
		{
			e.t = 0;
			e.muc = i;
			e.nod = Trie[0][i];
			
			Q.push(e);
		}
	
	while(Q.empty() == false)
	{
		e = Q.front(); Q.pop();
		
		baga_atm(e.t, e.muc, e.nod);
		
		for(i=0; i<3; ++i)
			if(Trie[e.nod][i])
			{
				new_e.t = e.nod;
				new_e.muc = i;
				new_e.nod = Trie[new_e.t][i];
				
				Q.push(new_e);
			}
	}
}

int main()
{
	freopen("abc2.in", "rt", stdin);
	freopen("abc2.out", "wt", stdout);
	
	scanf("%s", &T);
	
	while(!feof(stdin))
	{
		scanf("%s", &P);
		
		baga_trie();
	}

	bf();
	
	int i, muc, n, st = 0;
	
	for(n=strlen(T), i=0; i<n; ++i)
	{
		muc = (int) T[i] - 'a';
		
		st = Autm[st][muc];
		
		SOL += Acc[st];
	}
	
	printf("%d", SOL);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}