Opis glavnog rešenja

Ideja rešenja je da najpre dodamo sve reči iz rečnika u prefiksno stablo, a zatim za svaku reč iz rečnika proverimo da li je složena. Funkcija koja proverava da li je reč složena će primiti koren prefiksnog stabla, reč koja se trenutno proverava, indeks karaktera u reči do kog se stiglo sa proverom, kao i broj reči iz rečnika koje su se javile unutar do sada obrađenog prefiksa reči koja se pretražuje.

Najpre se krećemo kroz karaktere reči koju proveravamo i ukoliko za trenutni karakter ne postoji odgovarajuća grana zaključujemo da ta reč nije složena. Kada naiđemo na čvor u kome se završava neka reč, to znači da smo došli do kraja jedne od reči na koju bi se potencijalno mogle nadovezati druge reči kako bi se dobila složena reč. Tada je potrebno pokrenuti funkciju ponovo sa pomerenim indeksom, kao i uvećanim brojem reči.

Ukoliko dođemo u nekom trenutku do čvora u kome se završava neka reč, a pritom važi da je brojač karaktera za jedan manji od dužine reči koju proveravamo i dodatno, ukoliko je broj reči veći od jedan, to znači da smo na putu do kraja reči koju proveravamo “pokupili” više reči i pritom one zajedno čine upravo proveravanu reč. Sve reči koje prođu proveru dodajemo u uređeni skup i na kraju ih ispisujemo u leksikografski rastućem poretku.

Najgora složenost se dobija za rečnik \(\mathcal{D} = \{a, aa, aaa, \ldots, aa \cdots a\}, |\mathcal{D}| = n\). Za svaki karakter neke reči imali bismo po jedan rekurzivni poziv, tj. vreme provere da li je neka reč složena je tada \[\begin{align*} T(1) &= O(1), \\ T(m) &= T(m-1) + T(m-2) + \ldots + T(1) + O(m), \\ \end{align*}\] gde je \(m\) dužina reči koju proveravamo. Rešavanjem rekurentne jednačine dobijamo da je složenost \(O(2^m)\). Ukupna složenost algoritma je tada \(\sum_{i=1}^n O(2^i) = O(2^n)\). Ipak, u realnim primenama rečnik će biti drugačiji, te će ova složenost biti daleko manja, pošto grananje vršimo samo na karakterima koji predstavljaju kraj reči, a takođe izlazimo iz funkcije ranije ukoliko u bilo kom trenutku zaključimo da trenutna reč nije složena.

#include <iostream>
#include <unordered_map>
#include <set>
#include <string>
#include <vector>

using namespace std;

struct Node
{
    bool end_node = false;
    unordered_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->end_node = true;
}

bool is_compound_word(Node *trie, const string &word, const int index, const int count)
{
    Node* node = trie;

    for (int i = index; i < word.length(); i++) {
        if (node->children.find(word[i]) == node->children.end()) {
            return false;
        }

        node = node->children[word[i]];

        if (node->end_node) {
            if (i == word.length() - 1) { 
                return count >= 1;
            }

            if (is_compound_word(trie, word, i + 1, count + 1)) {
                return true;
            }
        }
    }

    return false;
}


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];
    }

    Node *trie = new Node();

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

    set<string> compound_words;
    for (const auto &word : words) {
        if (is_compound_word(trie, word, 0, 0)) {
            compound_words.insert(word);
        }
    }

    for (const auto &word : compound_words) {
        cout << word << " ";
    }
    cout << endl;

    free(trie);

    return 0;
}