Cod sursa(job #1234516)

Utilizator andreioneaAndrei Onea andreionea Data 27 septembrie 2014 15:08:34
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iostream>
#include <string>
#include <cctype>

struct TrieNode{
	TrieNode();
	int addWord(const char*);
	TrieNode* next[26];
	bool upper, lower;
	~TrieNode();
};

TrieNode::TrieNode() : upper(false), lower(false)
{
	for (int i = 0; i < 26; ++i)
		next[i] = 0;
}
int TrieNode::addWord(const char* word)
{
	unsigned long rez = 0;
	TrieNode* node = this;
	while (*word){
	char idx = std::tolower(*word) - 'a';
	bool islow = std::islower(*word);
	bool isup = std::isupper(*word);
	TrieNode* nextNode = node->next[idx];
	if (!nextNode) {
		nextNode = new TrieNode();
		node->next[idx] = nextNode;
		if (islow)
			node->lower = true;
		else
			node->upper = true;
		++rez;
	}
	else 
		if((islow && !lower) || 
			(isup && !upper))
		{
			++rez;
			if (islow)
				node->lower = true;
			else
				node->upper = true;
		}
	node = nextNode;
	++word;
	//nextNode->addWord(word + 1, rez);
	}
	return rez;
}

TrieNode::~TrieNode()
{
	for (int i = 0; i < 26; ++i)
		delete next[i];
}


int main()
{
	std::ifstream f("dictree.in");
	int n;
	unsigned long rez = 1;
	char line[105];
	TrieNode tn;
	f >> n;
	f.get();
	for (int i = 0; i < n; ++i) {
		f.getline(line, 101);
		rez += tn.addWord(line);
	}
	f.close();
	std::ofstream g("dictree.out");
	g << rez << "\n";
	g.close();
	return 0;
}