Autocomplete

Implementirati funkcionalnost automatskog kompletiranja reči koja se unosi sa tastature. Neka je dat rečnik podržanih reči i jedna reč (prefiks). Naći sve reči iz skupa podržanih reči koje počinju datim prefiksom.

Opis ulaza

Sa standardnog ulaza se unosi ceo broj \(n\) (\(1 \leq n \leq 100000\)), a zatim u narednom redu i \(n\) niski koje čine rečnik podržanih reči. Nakon toga, unosi se jedna reč koja predstavlja zadati prefiks.

Opis izlaza

Na standardni izlaz ispisati sve reči iz rečnika podržanih reči koje počinju zadatim prefiksom, uređene leksikografski rastuće. U slučaju da ne postoji ni jedna takva reč, ispisati \(-1\).

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Naivna implementacija ove funkcionalnosti podrazumeva čuvanje svih mogućih prefiksa kao ključeva u mapi i njihovo preslikavanje u liste reči koje pripadaju rečniku i mogu se dobiti dopunjavanjem datog prefiksa. Ovakav pristup je pre svega prostorno neefikasan - za svaki mogući prefiks čuvamo po listu reči.

Pristup koji donosi bolje performanse uključuje čuvanje reči iz rečnika u prefiksnom stablu. Pri ovakvoj implementaciji, dovoljno je spustiti se kroz stablo duž grana koje odgovaraju karakterima u datom prefiksu, a zatim kada stignemo do poslednjeg čvora na tom putu, pokrenuti obilazak podstabla iz datog čvora i ispisati sve reči iz tog podstabla.

Bitno je napomenuti da je za ovakav pristup potrebno u svakom čvoru čuvati uređenu mapu koja slika karaktere u njegove potomke, kako bi bilo moguće proći kroz tu kolekciju u leksikografskom poretku. Takođe, potrebno je za svaki čvor u kome se završava neka reč čuvati i tu reč radi ispisa.

Složenosti je u najgorem slučaju O\((nL)\), gde je \(n\) broj reči u stablu, a \(L\) dužina najduže reči iz rečnika, i ona se dostiže ukoliko obilazak podstabla pokrenemo iz korena stabla.

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

struct Node
{
    bool end_node = false;
    string word = "";
    map <char, Node *> children;
};

void add(Node *trie, const string &key)
{
    for (const auto c : key) {
        if (trie->children.find(c) == trie->children.end()) {
            trie->children[c] = new Node();
        }
        trie = trie->children[c];
    }

    trie->word = key;
    trie->end_node = true;
}

void print(Node *trie)
{
    if (trie->end_node) {
        cout << trie->word << endl;
    }

    for (auto [_, node] : trie->children) {
        print(node);
    }
}

void autocomplete(Node *trie, const string &prefix)
{
    for (const auto c : prefix) {
        if (trie->children.find(c) == trie->children.end()) {
            cout << -1 << endl;
            return;
        }
        trie = trie->children[c];
    }

    print(trie);
}

void free(Node *trie)
{
    if (trie != nullptr) {
        for (auto [_, node] : trie->children) {
            free(node);
        }
        delete trie;
    }
}

int main ()
{
    int n; cin >> n;

    vector<string> words(n);
    for(int i = 0; i < n; i++) {
        cin >> words[i];
    }

    string prefix; cin >> prefix;

    Node *trie = new Node();

    for (const auto &word : words) {
        add(trie, word);
    }

    autocomplete(trie, prefix);

    free(trie);

    return 0;
}