Najveći zajednički prefix

Konstruisati algoritam koji za datih \(n\) reči pronalazi najduži zajednički prefiks.

Opis ulaza

Sa standardnog ulaza se unosi vrednost \(n\), a zatim i \(n\) reči.

Opis izlaza

Na standardni izlaz ispisati najduži zajednički prefiks svih \(n\) reči.

Primer 1

Ulaz

4
code
codecs
coder
coding

Izlaz

cod

Primer 2

Ulaz

4
core
more
come
door

Izlaz

Rešenje

Opis glavnog rešenja

Prvi korak rešenja podrazumeva da sve reči koje su učitane sa standardnog ulaza ubacimo u prefiksno stablo. Kada to uradimo, nalaženje najdužeg zajedničkog prefiksa se svodi na obilazak stabla iz korena sve dok u trenutnom čvoru imamo samo jedno dete ili dok ne naiđemo na čvor u kome se završava neka reč. Onog trenutka kada naiđemo na račvanje, odnosno čvor sa barem dva deteta, znamo da od tog trenutka postoje barem dva odvojena prefiksa, pa moramo prekinuti dalje traženje. Bitno je napomenuti da ukoliko u pretrazi u bilo kom trenutku naiđemo na čvor u kome se završava neka od reči, a pritom su svi čvorovi do tad imali samo jedno dete, upravo reč koja se završava u tom listu predstavlja najduži zajednički prefiks. Razmotriti primer reči: Ana, Anastasija, Anastasijin. Ako bismo samo išli do prvog račvanja, dobili bismo Anastasij kao prefiks, tako da je vrlo bitno zaustaviti se kada dođemo do čvora u kome se završava neka reč.

Složenost dodavanja \(n\) reči u prefiksno stablo je \(O(n M)\), gde je \(M\) dužina najduže reči, dok je složenost nalaženja najdužeg zajedničkog prefiksa \(O(M)\), pa je ukupna složenost algoritma \(O(n M)\).

#include <iostream>
#include <unordered_map>
#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;
}

string longest_common_prefix(Node *trie)
{
    string prefix;

    while(!trie->end_node && trie->children.size() == 1) {
        auto [c, node] = *trie->children.begin();

        prefix += c;
        trie = node;
    }

    return prefix;
}

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

    cout << longest_common_prefix(trie) << endl;

    free(trie);

    return 0;
}