Cod sursa(job #3156198)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 10 octombrie 2023 20:20:09
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int wordCount = 0, endCount = 0;
    vector <Node*> letters;

    Node()
    {
        letters.resize(26, NULL);
    }
};

Node* insertWord(Node *&node, string &s, int p = 0)
{
    if(node == NULL)
    {
        node = new Node;
    }

    node->wordCount ++;

    if(p == s.size())
    {
        node->endCount ++;
        return node;
    }

    node->letters[s[p] -'a'] = insertWord(node->letters[s[p] - 'a'], s, p + 1);
    return node;
}

Node* eraseWord(Node *&node, string &s, int p = 0)
{
    if(p == s.size())
        node->endCount --;
    else
        node->letters[s[p] -'a'] = eraseWord(node->letters[s[p] - 'a'], s, p + 1);

    node->wordCount --;
    if(node->wordCount == 0)
    {
        delete(node);
        node = NULL;
    }

    return node;
}

int findWord(Node *node, string &s, int p = 0)
{
    if(node == NULL)
        return 0;

    if(p == s.size())
        return node->endCount;

    findWord(node->letters[s[p] - 'a'], s, p + 1);
}

int findPrefix(Node *node, string &s, int p = 0)
{
    if(p == s.size()  ||  node->letters[s[p] - 'a'] == NULL)
        return p;
//    if(node == NULL)
//        return p - 1;

    findPrefix(node->letters[s[p] - 'a'], s, p + 1);
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

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

    Node* trie = NULL;
    int op;
    string s;
    while(cin >> op >> s)
    {
        if(op == 0)
        {
            insertWord(trie, s);
        }
        else if(op == 1)
        {
            eraseWord(trie, s);
        }
        else if(op == 2)
        {
            cout << findWord(trie, s) << "\n";
        }
        else if(op == 3)
        {
            cout << findPrefix(trie, s) << "\n";
        }
    }
    return 0;
}