Cod sursa(job #3159500)

Utilizator SSKMFSS KMF SSKMF Data 21 octombrie 2023 14:23:22
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <fstream>
using namespace std;

ifstream cin ("trie.in");
ofstream cout ("trie.out");

class Trie {
    private:
        int total = 0 , aparitii = 0; Trie *urmatorul[26] = {};
    public:
        void add (char *cuvant , int indice = 0) 
        {
            total++;
            if (cuvant[indice])
            {
                if (!urmatorul[cuvant[indice] - 'a'])
                    urmatorul[cuvant[indice] - 'a'] = new Trie;

                urmatorul[cuvant[indice] - 'a'] -> add(cuvant , indice + 1);
                return;
            }

            aparitii++;
        }
        void subtract (char *cuvant , int indice = 0) 
        {
            total--;
            if (cuvant[indice])
            {
                urmatorul[cuvant[indice] - 'a'] -> subtract(cuvant , indice + 1);
                if (!urmatorul[cuvant[indice] - 'a'] -> total)
                    { delete urmatorul[cuvant[indice] - 'a']; urmatorul[cuvant[indice] - 'a'] = NULL; }

                return;
            }

            aparitii--;
        }
        int find (char *cuvant , int indice = 0) 
        {
            if (cuvant[indice])
            {
                if (!urmatorul[cuvant[indice] - 'a'])
                    return 0;

                return urmatorul[cuvant[indice] - 'a'] -> find(cuvant , indice + 1);
            }

            return aparitii;
        }
        int prefix (char *cuvant , int indice = 0) 
        {
            if (cuvant[indice] && urmatorul[cuvant[indice] - 'a'])
                return urmatorul[cuvant[indice] - 'a'] -> prefix(cuvant , indice + 1);
                
            return indice;
        }
} trie;

int main ()
{
    char cuvant[21];
    for (short tip ; cin >> tip >> cuvant ; )
        switch (tip)
        {
            case 0: trie.add(cuvant);
                break;

            case 1: trie.subtract(cuvant);
                break;

            case 2: cout << trie.find(cuvant) << '\n';
                break;

            case 3: cout << trie.prefix(cuvant) << '\n';
                break;
        }

    cout.close(); cin.close();
    return 0;
}