Cod sursa(job #336721)

Utilizator prdianaProdan Diana prdiana Data 1 august 2009 12:23:00
Problema Trie Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <stdio.h>
#include <string.h>

struct Trie
{
	Trie *nxt[26];
	int nr;
	int nrf;
	Trie();
};

Trie::Trie()
{
	nr = 0;
	nrf = 0;
	memset(nxt,0,sizeof(nxt));
}

Trie *t = new Trie;
Trie *r = t;
char s[32];
int i,l,max;
inline void insert()
{
	l=strlen(s);
	t = r;
	for (i=0;i<l;i++)
	{
		t->nrf++;
		if (t->nxt[s[i]-'a'] == 0)
		{
			t->nxt[s[i]-'a'] = new Trie;
			t->nxt[s[i]-'a']->nr = 0;
		}
		if (i==l-1)
		{
			t->nxt[s[i]-'a']->nr++;
			t->nxt[s[i]-'a']->nrf++;
		}
		t = t->nxt[s[i]-'a'];
	}
}

inline void del()
{
	l=strlen(s);
	t = r;
	for (i=0;i<l;i++)
	{
		if (t->nxt[s[i]-'a'] == 0)
		{
			return;
		}
		t = t->nxt[s[i]-'a'];
	}
	if (t->nr>0)
	{
		t->nr--;
		t = r;
		for (i=0;i<l;i++)
		{
			t->nrf--;
			t = t->nxt[s[i]-'a'];
		}
		t->nrf--;
	}
}

inline void prefix()
{
	l=strlen(s);
	t = r;
	max = 0;
	for (i=0;i<l;i++)
	{
		if (t->nrf>0)
		{
			max = i;
		}
		if (t->nxt[s[i]-'a'] == 0)
		{
			printf("%d\n",max);
			return;
		}
		t = t->nxt[s[i]-'a'];
	}
	if (t->nrf > 0)
	{
		printf("%d\n",l);
	}
	else
	{
		printf("%d\n",max);
	}
}

inline void type()
{
	l=strlen(s);
	t = r;
	for (i=0;i<l;i++)
	{
		if (t->nxt[s[i]-'a'] == 0)
		{
			printf("0\n");
			return;
		}
		t = t->nxt[s[i]-'a'];
	}
	printf("%d\n",t->nr);
}

int main()
{
	freopen("trie.in","r",stdin);
	freopen("trie.out","w",stdout);
	int op;
	while (!feof(stdin))
	{
		memset(s,0,sizeof(s));

		scanf("%d %s",&op,&s);
		if (strlen(s)>0)
		switch(op)
		{
		case 0:
			insert();break;
		case 1:
			del();break;
		case 2:
			type();break;
		case 3:
			prefix();break;
		}
	}
	t= r;

	return 0;
}