Cod sursa(job #1483232)

Utilizator razyelxrazyelx razyelx Data 8 septembrie 2015 23:12:37
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.02 kb
#include <fstream>
#include <string>

using namespace std;
class Node {
    public:
        Node* children[26];
        int count = 0;
        int words = 0;
        Node() {
            for (int i = 0; i <= 26; i++) { children[i] = 0; }
        }
};

class Trie {

    private:
             
        Node* locate(string word) {
            Node* current = &root;
            for (int i = 0; i < word.size(); i++) {
                if (current->children[word.at(i) - 97]) {
                    current = current->children[word.at(i) - 97];
                } else {
                    return NULL;
                }
            }
            if (current == &root)
                return NULL;
            return current;
        }
        
    public:
        Node root;

        void add(string word) {
            Node* current = &root;
            for (int i = 0; i < word.length(); i++) {
                if (!current->children[word.at(i) - 97]) {
                    current->children[word.at(i) - 97] = new Node();
                }
                current = current->children[word.at(i) - 97];
                current->words++;
            }
            current->count++;
            current->words--;

        }

        void remove(string word) {
            Node * current = &root;
            Node * parent = NULL;
            int len = word.size();
            for (int i = 0; i <= len; i++) {
                current->words--;
                current->count--;
                if (current->words <= 0 && current->count <= 0 && current != &root) {
                    Node * tmp = current;
                    parent->children[word.at(i-1) - 97] = NULL;
                    if (i < len) {
                        parent = current;
                        current = current->children[word.at(i) - 97];
                    }
                    delete tmp;
                } else if (i < len) {
                    parent = current;
                    current = current->children[word.at(i) - 97];
                }
            }
        }
        
        int count(string word) {
            Node* current = locate(word);
            if (current) {
                return current->count;
            }
            return 0;
        }
        
        int logest_prefix(string word) {
            for (int i = word.size(); i >= 0 ; i--) {
                string prefix = word.substr(0, i);
                Node* node = this->locate(prefix);
                if (node && (node->count > 0 || node->words > 0)) {
                    return i;
                }
            }
            return 0;
        }
        
};

int main()
{
    ifstream fin("trie.in");
    ofstream fout("trie.out");

    Trie words;
    string word;
    int op = -3;
    while (fin>>op>>word) {
        if (op == 0) {
            words.add(word);
        } else if (op == 1) {
            words.remove(word);            
        } else if (op == 2) {
            fout<<words.count(word)<<endl;
        } else if ( op == 3) {
            fout<<words.logest_prefix(word)<<endl;
        }
    }

    return 0;
}