Cod sursa(job #2454573)

Utilizator ShayVincent Cervoni Shay Data 9 septembrie 2019 11:38:33
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <bits/stdc++.h>

const int ALPHABET_SIZE = 26;

template <typename T> class Trie {
private:
	int count;
	std::vector<Trie<T>*> children;
	bool isEndOfWord;
public:
	Trie() {}

	Trie(int capacity): 
		count(0), children(capacity, NULL) {}

	void insert(std::string key) {
		Trie *temp = this;
		unsigned int len = key.length();

		for (unsigned int i = 0 ; i < len ; ++i) {
			int index = key[i] - 'a';
			
			if (temp->children[index] == NULL) {
				temp->children[index] = new Trie(ALPHABET_SIZE);
			}

			temp = temp->children[index];
		}

		++(temp->count);
		temp->isEndOfWord = true;
	}

	void remove(std::string key) {
        Trie *temp = this;
        unsigned int len = key.length();

        for (unsigned int i = 0 ; i < len; ++i) {
            int index = key[i] - 'a';
            if (temp->children[index] == NULL) {
                return;
            }

            temp = temp->children[index];
        }

        if (temp && temp->isEndOfWord) {
            temp->count = 0;
            temp->isEndOfWord = false;
        }
    }

    int search(std::string key) {
        Trie *temp = this;
        unsigned int len = key.length();

        for (unsigned int i = 0 ; i < len ; ++i) {
            int index = key[i] - 'a';
            if (temp->children[index] == nullptr) {
                return false;
            }
            temp = temp->children[index];
        }

        return temp->count;
    }

    int len_longest_common_preifx(std::string prefix) {
    	Trie *temp = this;
		int cnt = 0;
		for (unsigned int i = 0 ; i < prefix.length() && temp->isEndOfWord == false; ++i, ++cnt) {
            int index = prefix[i] - 'a';
            
            if (temp->children[index] == NULL) {
                break;
            }

            temp = temp->children[index];
        }

        return cnt;
    }
};

int main() {
	std::ifstream cin("trie.in");
	std::ofstream cout("trie.out");
	std::ios::sync_with_stdio(false);

	Trie<int> *trie = new Trie<int>(ALPHABET_SIZE);
	int test_case;
	std::string line;

	while (cin >> test_case, cin >> line) {
		switch (test_case) {
			case 0: trie->insert(line); break;
			case 1: trie->remove(line); break;
			case 2: cout << trie->search(line) << '\n'; break;
			case 3: cout << trie->len_longest_common_preifx(line) << '\n'; break;
			default: break;
		}
	}

	delete trie;
	return 0;
}