Cod sursa(job #1691460)

Utilizator vasica38Vasile Catana vasica38 Data 18 aprilie 2016 13:47:43
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<string>
#include<string.h>
#define f(X) X-48
using namespace std;

ifstream cin("trie.in");
ofstream cout("trie.out");

struct trie
{
	int pre, cuv;
	trie *a[26];
	trie()
	{
		pre = 0;
		cuv = 0;
		memset(a, 0, sizeof(a));
	}
};

trie * root = new trie();


void insert(string s)
{
	trie *p = root;
	for (int i = 0; i < s.size(); ++i)
	{
		if (!p->a[s[i] - '0']) p->a[s[i] - '0'] = new trie();
		p = p->a[s[i] - '0'];
		//p->pre++;
	}
	++p->cuv;
}


void del(string s)
{
	trie *p = root;
	for (int i = 0; i < s.size(); ++i)
	{
		p = p->a[s[i] - '0'];
		--p->pre;
	}
	--p->cuv;
}

int query(string s)
{
	trie *p = root;
	for (int i = 0; i < s.size(); ++i)
	{
		if (p->a[s[i] - '0']) p = p->a[s[i] - '0'];
		else
			return 0;
	}
	return p->cuv;
}

int pre(string s)
{
	trie *p = root;
	int sol = 0;
	for (int i = 0; i < s.size(); ++i)
	{
		if (!p->a[s[i] - '0']) return sol;
		p = p->a[s[i] - '0'];
		if (p->pre) sol = i + 1;
	}
	return sol;

}

int main()
{
	string s;
	int x;
	while (cin >> x >> s)
	{
		if (!x) insert(s);
		if (x == 1) del(s);
		if (x == 2) cout << query(s) << "\n";
		if (x == 3) cout << pre(s) << "\n";
	}
	return 0;
}