Cod sursa(job #229873)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 11 decembrie 2008 23:02:39
Problema Trie Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
using namespace std;

#include <queue>
#include <fstream>
#include <bitset>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define mp make_pair

typedef pair<int,char> pc;
typedef vector< vector<pc> > VM;

#define IN  "trie.in"
#define OUT "trie.out"

VM A(1);
vector<int> S(1),NR(1);
int size=1,next,type;
string word; 

II void add(int nod,int hg)
{
	int poz = hg;
	++S[nod];
	FOR(i,0,(int)A[nod].sz()-1)
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
			{
				++NR[nod];
				return;
			}	
			add(A[nod][i].f,hg+1);
			return;
		}	
	
	if(poz+1 > (int)word.sz() )
	{
		++NR[nod];
		return;
	}
	A[nod].pb( mp(++next,word[poz]) );
	if(size == next)
	{
		A.resize(size<<=1);
		S.resize(size);
		NR.resize(size);
	}	
	add(next,hg+1);
}

II bool clear(int nod,int hg)
{
	int poz = hg;
	--S[nod];
	FOR(i,0,(int)A[nod].sz()-1)
	{
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
			{
				--NR[nod];
				return S[nod];
			}	
			if(!clear(A[nod][i].f,hg+1) )
				A[nod][i].s = 0;
			return S[nod];
		}	
	}
	if(poz+1 > (int)word.sz() )
		--NR[nod];
	return S[nod];
}

II int querry(int nod,int hg)
{
	int poz = hg;
	
	FOR(i,0,(int)A[nod].sz()-1)
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
				return NR[nod];
			return querry(A[nod][i].f,hg+1);
		}	
	
	if(poz+1 > (int)word.sz() )
		return NR[nod];
	return 0;
}

II int lcp(int nod,int hg)
{
	int poz = hg;
	
	FOR(i,0,(int)A[nod].sz()-1)
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
				return hg;
			return lcp(A[nod][i].f,hg+1);
		}	
	return hg;
}

int main()
{
	ifstream fin("trie.in");  
	freopen(OUT,"w",stdout);
	
	for(;fin >> type >> word;)  
	{
		if(type == 0)
			add(0,0);
		if(type == 1)
			clear(0,0);
		if(type == 2)	
			printf("%d\n", querry(0,0) );
		if(type == 3)
			printf("%d\n", lcp(0,0) );
	}	
	
	return 0;
}