Cod sursa(job #2627907)

Utilizator RobertLearnsCDragomir Robert. RobertLearnsC Data 13 iunie 2020 12:30:10
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
public function promoteUser(Request $request) {
    $user = User::find($request->input('userId'));
    $group = Group::find($request->input('groupId'));

    // Utilizatorul primeste rank de profesor in clasa respectiva
    $group->users()->save($user->id, ['is_teacher' => 1]);

    return redirect()->back();
}
#include <bits/stdc++.h>
using namespace std;
#define ch (word[0] - 'a')

string next(string word) {
    word = word.erase(0, 1);
    return word;
}

struct Trie {
    int sons = 0, cnt = 0;
    Trie *son[(int)('z') - (int)('a') + 5] = {0};
};
Trie *tree = new Trie;

void insert(Trie *node, string word)
{
    if(!word.size()) {
        node->cnt++;
    } else {
        if (!node->son[ch]) {
            node->son[ch] = new Trie;
            node->sons++;
        }
        insert(node->son[ch], next(word));
    }
}

int dilit(Trie *node, string word)
{
    if(!word.size()) {
        node->cnt--;
    } else if(dilit(node->son[ch], next(word))) {
        node->son[ch] = 0;
        node->sons--;
    }
    if(!node->cnt && !node->sons && node != tree) {
        delete node;
        return 1;
    }
    return 0;
}

int query(Trie *node, string word) {
    if(!word.size()) {
        return node->cnt;
    }
    if(node->son[ch]) {
        return query(node->son[ch], next(word));
    }
    return 0;
}

int find_longest_prefix(Trie *node, string word, int length)
{
    if(!node->son[ch] || !word.size()) {
        return length;
    }
    return find_longest_prefix(node->son[ch], next(word), length + 1);
}

int main() {
    ifstream in("trie.in");
    freopen("trie.out", "w", stdout);

    string line;
    while(getline(in, line)) { /// stocam toata linia in "line" iar line[0] va reprezenta operatia si &line[2] va reprezenta cuvantul
        switch(line[0]) {
            case '0':
                insert(tree, &line[2]);
                break;
            case '1':
                dilit(tree, &line[2]);
                break;
            case '2':
                printf("%d\n", query(tree, &line[2]));
                break;
            case '3':
                printf("%d\n", find_longest_prefix(tree, &line[2], 0));
                break;
        }
    }
    return 0;
}