Trie TST. Compta les claus que comencen per algun dels caràcters donats. X97406

Donada la classe $dicc$ que permet gestionar diccionaris on només hi guardem claus úniques usant tries implementats amb la tècnica d’arbres ternaris de cerca (TST), cal implementar el mètode

  nat quantes_comencen(string inicials) const;
  // Pre: inicials no conté el char '\#'
  // Post: Retorna el nº de claus que comencen per algun dels caràcters que conté inicials

Les claus són del tipus string i els símbols utilitzats per construir el trie són els chars de les claus. S’ha usat el char especial ’#’ per indicar la fi de la clau.

Cal enviar a jutge.org la següent especificació de la classe $dicc$ i la implementació del mètode dins del mateix fitxer. La resta de mètodes públics i privats ja estan implementats.

#include <iostream>
using namespace std;
typedef unsigned int nat;

class dicc {
  public:
    dicc();  // Constructora per defecte. Crea un diccionari buit.

    ~dicc(); // Destructora

    // Insereix la clau k en el diccionari. Si ja hi era, no fa res.
    void insereix(const string &k);

    nat quantes_comencen(string inicials) const;
    // Pre: inicials no conté el char '\#'
    // Post: Retorna el nº de claus que comencen per algun dels caràcters que conté inicials

  private:
    struct node {
      char _c;    // Símbol posició i-èssima de la clau
      node* _esq; // Fill esquerra, apunta a símbols mateixa posició formant un BST
      node* _cen; // Fill central, apunta a símbols següent posició
      node* _dre; // Fill dret, apunta a símbols mateixa posició formant un BST
      node(const char &c, node* esq = NULL, node* cen = NULL, node* dre = NULL);
    };
    node* _arrel;
    static void esborra_nodes(node* t);
    static node* insereix(node *t, nat i, const string &k);

    // Aquí va l'especificació dels mètodes privats addicionals
};

// Aquí va la implementació del mètode públic quantes\_comencen i privats addicionals

Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació del mètode $quantes\_comencen$ (el que normalment estarien separats en els fitxers $.hpp$ i $.cpp$).

Per testejar la classe disposes d’un programa principal que insereix claus en un diccionari i després compta quantes comencen per algun dels caràcters de diferents strings.

Entrada

L’entrada conté dos blocs separats per una línia amb 10 guions (———–). El primer bloc consisteix en una llista de strings: són les claus que tindrà el diccionari. El segon bloc consisteix en una altra llista de strings: cada string conté els caràcters inicials de les claus que volem comptar del diccionari.

Sortida

Per a cada string d’entrada del segon bloc, escriu una línia amb el nombre de claus que comencen per algun dels caràcters que conté aquest string, el text " comencen per " i l’string d’entrada.

Observació

Només cal enviar la classe requerida i la implementació del mètode $quantes\_comencen$. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Per superar els jocs de prova privats, el mètode $quantes\_comencen$ ha de visitar només els nodes del trie imprescindibles.