Cod sursa(job #578718)

Utilizator chibicitiberiuChibici Tiberiu chibicitiberiu Data 11 aprilie 2011 15:31:17
Problema Trie Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.96 kb
#include <stdio.h>
#include <stack>
#include <string.h>
using namespace std;

class Node
{
public:
    int IsEnd;
    Node* Children[26];
    int Count;
    int Depth;

    inline void Common()
    {
        memset(Children, 0, sizeof(Node*)*26);
        Count = 0;
    }

    Node() { IsEnd=Depth=0; Common(); }
    Node(int end) {IsEnd=end; Depth=0; Common(); }
    Node(int end, int d) { IsEnd=end; Depth=d; Common(); }

};


class Trie
{
    Node root;

    int _remove (Node* node, char* s)
    {
        int Continue = 1;

        if (node == NULL) return 0;

        if (*s == 0 || *s=='\n') {
            node->IsEnd--;
        }

        else {
            Continue = _remove(node->Children[*s - 'a'], s+1);
            if (!Continue) return 0;
            delete node->Children[*s - 'a'];
            node->Children[*s - 'a'] = NULL;
            node->Count--;
        }

        if (node->Count > 0 || node->IsEnd > 0) return 0;
        return 1;
    }

public:

    void Insert (char* str)
    {
        int len = strlen(str), i=0;

        // Find last node
        Node* wh = &root;
        Node* parent = &root;

        for (i=0; wh != NULL && i < len; i++)
        {
            parent = wh;
            wh = wh->Children[str[i] - 'a'];
        }
        
        if (wh == NULL)
        {
            for (--i; i < len-1; i++)
            {
                parent->Children[str[i] - 'a'] = new Node(0, parent->Depth+1);
                parent->Count++;
                parent = parent->Children[str[i] - 'a'];
            }

            parent->Children[str[len-1] - 'a'] = new Node(1, parent->Depth+1);
            parent->Count++;
        }

        else wh->IsEnd++;
    }

    int Count (char* str)
    {
        int len = strlen(str), i=0;

        // Find last node
        Node* wh = &root;

        for (i=0; wh != NULL && i < len; i++)
            wh = wh->Children[str[i] - 'a'];

        if (wh == NULL) return 0;
        return wh->IsEnd;
    }

    void Remove (char* str)
    {
        _remove(&root, str);
    }

    int LongestCommonPrefix (char* str)
    {
        int len = strlen(str), i=0;

        // Find last node
        // Find last node
        Node* wh = &root;
        Node* parent = &root;

        for (i=0; wh != NULL && i <= len; i++)
        {
            parent = wh;
            if (str[i] == 0 || str[i] == '\n' ) wh = NULL;
            else wh = wh->Children[str[i] - 'a'];
        }

        return i-1;
    }

};


int main()
{
    Trie t;

    freopen ("trie.in", "r", stdin);
    freopen ("trie.out", "w", stdout);

    int operation;
    char param[22];

    while (scanf("%d %s\n", &operation, param) != EOF)
    {
        switch (operation)
        {
            case 0: t.Insert(param);
                break;
            case 1: t.Remove(param);
                break;
            case 2: printf ("%d\n", t.Count(param));
                break;
            case 3: printf ("%d\n", t.LongestCommonPrefix(param));
                break;
        }
    }

    return 0;
}