Cod sursa(job #1343844)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 15 februarie 2015 23:19:38
Problema Trie Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;

ifstream is("trie.in");
ofstream os("trie.out");

const int val = 26;
char sir[26];

struct Node
{
    Node()
    {
        nr_cuv = nr_sons = 0;
        memset( sons, 0, sizeof(sons));
    }
    int nr_cuv, nr_sons;
    Node* sons[26];
};

Node* T = new Node;

void Insert( Node* T, char *s );
bool Delete( Node* T, char *s );
int Nr( Node* T, char *s );
int Prefix( Node* T, char *s, int nr );

int main()
{
    while(is.getline(sir, 26 ) )
    {
        switch( sir[0] )
        {
            case '0': Insert( T, sir + 2 ); break;
            case '1': Delete( T, sir + 2 ); break;
            case '2': os << Nr( T, sir + 2 ) << '\n'; break;
            case '3': os << Prefix( T, sir + 2, 0 ) << '\n'; break;
        }
    }
    is.close();
    os.close();
    return 0;
}

void Insert( Node* node, char *s )
{
    if(*s == '\0' )
    {
        node->nr_cuv++;
        return;
    }
    if( node->sons[*s-'a'] == 0 )
    {
        node->sons[*s-'a'] = new Node;
        node->nr_sons++;
    }
    Insert(node->sons[*s-'a'], s+1);
}

bool Delete( Node* node, char *s )
{
    if( *s == '\0' )
        node->nr_cuv--;
    else
        if( Delete(node->sons[*s-'a'], s+1))
        {
            node->sons[*s-'a'] = 0;
            node->nr_sons--;
        }
    if ( node->nr_cuv == 0 && node->nr_sons == 0 && T != node )
    {
        delete node;
        return true;
    }
    return false;
}

int Nr( Node* node, char *s )
{
    if( *s == '\0' )
        return node->nr_cuv;
    if( node->sons[*s-'a'] )
        return Nr( node->sons[*s-'a'], s+1 );
    return 0;
}

int Prefix( Node* node, char *s, int nr )
{
    if( *s == '\0' )
        return nr;
    if( node->sons[*s-'a'] == 0 )
        return nr;
    Prefix( node->sons[*s-'a'], s+1, nr + 1 );
}