Cod sursa(job #2461199)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 25 septembrie 2019 01:17:46
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");

struct trie
{

	int cuvinte=0;
	vector <trie*> son;
	vector <char> edge;
	trie* father=NULL;

};

trie* head = new trie;

void add(string& str)
{
	int i, j, n, m;
	bool check = false;
	m = str.size();
	trie* temp = head;
	for (j = 1; j < m; j++)
	{
		check = false;
		n = (*temp).edge.size() - 1;
		for (i = 0; i <= n; i++)
		{
			if ((*temp).edge[i] == str[j])
			{
				check = true;
				temp = (*temp).son[i];
				break;
			}
		}
		if (check == false)
		{
			n++;
			(*temp).son.push_back(new trie);
			temp->edge.push_back(str[j]);
			(*(*temp).son[n]).father=temp;
			temp = temp->son[n];
		}



	}
	temp->cuvinte++;


}

void delet(string& str)
{
	int i, j, n, m;
	m = str.size();
	trie* temp = head;
	trie* aux_pointer = NULL;
	for (j = 1; j < m; j++)
	{
		n= (*temp).edge.size() - 1;
		for (i = 0; i <= n; i++)
		{
			if ((*temp).edge[i] == str[j])
			{
				temp = (*temp).son[i];
				break;
			}
		}
	}
	temp->cuvinte--;

	while (temp->cuvinte == 0 && temp->father != NULL)
	{
		aux_pointer = temp->father;
		n = aux_pointer->edge.size() - 1;
		
		for (i = 0; i <= n; i++)
		{
			if (aux_pointer->son[i] == temp)
			{
				aux_pointer->edge[i] = aux_pointer->edge[n];
				aux_pointer->edge.pop_back();
				aux_pointer->son[i] = aux_pointer->son[n];
				aux_pointer->son.pop_back();
				break;
			}
		}
	
		delete temp;
		temp = aux_pointer;
		if (n >= 1) return;
	}

}


void nr_cuvinte(string& str)
{
	int i, j, n, m;
	m = str.size();
	trie* temp = head;
	for (j = 1; j < m; j++)
	{
		n = (*temp).edge.size() - 1;
		for (i = 0; i <= n; i++)
		{
			if ((*temp).edge[i] == str[j])
			{
				
				temp = (*temp).son[i];
				break;
			}
		}
		



	}
	g << temp->cuvinte << endl;

}


void longest_prefix(string& str)
{
	int i, j, n, m;
	m = str.size();
	bool check = false;
	int nr = 0;
	trie* temp = head;
	for (j = 1; j < m; j++)
	{
		check = false;
		n = (*temp).edge.size() - 1;
		for (i = 0; i <= n; i++)
		{
			if ((*temp).edge[i] == str[j])
			{
				nr++;
				check = true;
				temp = (*temp).son[i];
				break;
			}
		}
		if (check == false)
		{
			g << nr << endl;
			return;
		}


	}
	g << nr << endl;
}




int main ()
{
	string str;
	int c = 0;
	while (!f.eof())
	{
		f >> c;
		getline(f, str);
		if (c == 0) add(str);
		if (c == 1) delet(str);
		if (c == 2) nr_cuvinte(str);
		if (c == 3) longest_prefix(str);

	}


	return 0;
}