Trie

Implementation

#include <bits/stdc++.h>
using namespace std;

// Εκφώνηση:
// Θα σας δείνεται ένα λεξικό απο Ν λέξεις.
// Στην συνέχεια θα σας δωθούν Q άλλες λέξεις και πρέπει να βρείτε αν ανήκουν
// στο λεξικό ή όχι.

// παράδειγμα εισόδου
/*
4
abcd
abb
ac
aaaa
3
aa
ac
abc
*/

// παράδειγμα εξόδου
/*
NO
YES
NO
*/

struct node {
    // Πίνακας απο δείκτες σε άλλους (παιδία) κόμβους του συγκεκριμένου κόμβου
    // του Trie. Έχουμε 26 lower case λατινικούς χαρακτήρες άρα θα έχουμε το
    // πολύ 26 παιδία αφού κάθε ακμή αναπαριστά την πρόσθεση ενός χαρακτήρα στο
    // τέλος της συμβολοσειράς μας.
    struct node *p[26];
    // Μεταβλητή που θα είναι αληθής εάν και μόνο εαν ο κόμβος μας είναι τέλος
    // λέξης.
    bool leksi;
};

int main() {

    // Δημιουργούμε τον αρχικό κόμβο του trie (η κενή συμβολοσειρά)
    // o default constructor θα δώσει όλες τις θέσεις του πίνακα start.p να
    // είναι ίσες με NULL (δηλαδή δεν δείχνουν πουθενά - άρα δεν υπάρχει ακμή
    // για το συγκεκριμένο γράμμα) επίσης η μεταβλητή start.leksi είναι false
    // (by default)
    node start = node();

    // Τώρα θα διαβάσουμε τις λέξεις και θα δημιουργήσουμε το λεξικό-trie
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {

        // Διαβάζουμε την λέξη
        string x;
        cin >> x;

        // Ξεκινούμε και για κάθε γράμμα της λέξης (ένα προς ένα)
        // το βάζουμε στο Trie ως ακμή στον τωρινό κόμβο.
        // Ξεκινούμε πάντα απο start. Άρα έχουμε δείκτη που να δείχνει στο
        // start. Το &start θα μας επιστρέψει την διεύθηνση του αρχικού κόμβου
        // την οποία θα αποθηκέυσουμε στον δείκτη μας. Θυμηθείται ότι ο pointer
        // είναι για να "δείχνει" σε διευθήνσεις μνήμης.
        node *torinos = &start;

        for (size_t j = 0; j < x.size(); j++) {

            // Ελέγχουμε εάν υπάρχει ακμή απο το τωρινό κόμβο για το γράμμα που
            // προσπαθούμε να προσθέσουμε
            if (torinos->p[x[j] - 'a'] == NULL) {
                // Εαν δεν υπάρχει πρέπει να δημιουργήσουμε τον κόμβο στον οποίο
                // θα δείχνει η ακμή. Το keyword "new" χρησιμοποιείται για να
                // δεσμεύσουμε καινούργια διεύθηνηση μνήμης για το instance του
                // struct μας και επιστρέφει δείκτη σε αυτήν την διεύθηνση.
                // Χωρίς new o constructor ναι μεν θα επέστρεφε καινούργιο
                // instance του node αλλά η μεταβλητή μας θα βρισκόταν στην ίδια
                // διεύθηνση με πριν το οποίο δεν θέλουμε να γίνει προφανώς.
                node *neos = new node();
                // Τώρα μπορούμε να βάλουμε την ακμή για το γράμμα μας να
                // δείχνει στον καινούργιο κόμβο
                torinos->p[x[j] - 'a'] = neos;
                // και ο καινούργιος κόμοβος γίνεται τώρα ο τωρινός στον οποίο
                // θα δείχνουμε
                torinos = neos;
            } else {
                // αφού η ακμή και ο κόμβος στον οποίο δέιχνει υπάρχει
                // πολύ απλά βάζουμε τον δείχτη μας να δείχνει σε αυτό τον κόμβο
                torinos = torinos->p[x[j] - 'a'];
            }
        }

        // Τώρα αφού έχουμε φτάσει να βάλουμε ακμή και για το τελευταίο γράμμα
        // της συμβολοσειράς x άρα σημαίνει δείχνουμε στον κόμβο που αναπαρτηστά
        // το x στο trie μας θέτουμε την μεταβλητή torinos->leksi σε true αφού
        // έχουμε λέξη.
        torinos->leksi = true;
    }

    // Τώρα πρέπει να ψάξουμε για κάθε μια απο τις Q λέξεις που θα μας δωθούν αν
    // υπάρχει στο Trie.
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {

        // Διαβάζουμε την συμβολοσειρά
        string x;
        cin >> x;

        // Ακολουθούμε γράμμα προς γράμμα και ελέγχουμε αν η συμβολοσειρά είναι
        // τελικά μέσα στο λεξικό μας ή όχι. Πάλι ξεκινούμε απο την ρίζα του
        // Trie (i.e. το start)
        node *torinos = &start;
        bool no_node = false;
        for (size_t j = 0; j < x.size(); j++) {

            if (torinos->p[x[j] - 'a'] == NULL) {
                // αν δεν υπάρχει η ακμή τότε σίγουρα η λέξη δεν είναι στο
                // λεξικό
                no_node = 1;
                break;
            } else {
                // διαφορετικά απλά ακολουθούμε την ακμή
                torinos = torinos->p[x[j] - 'a'];
            }
        }

        // αν δεν βρήκαμε κόμβο ή ο κόμβος δεν είναι κόμβος λέξης τότε τυπώνουμε
        // ΝΟ
        if (no_node || !(torinos->leksi)) {
            cout << "NO" << endl;
            continue;
        }

        // διαφορετικά αφου ακολουθήσαμε το μονοπάτι που ορίζεται απο τα
        // γράμματα της συμβολοσειράς που ψάχνουμε και φτάσαμε σε κόμβο όπου
        // έχουμε σημειώσει ότι κάποια λέξη τελείωνει σε αυτόν τότε ξέρουμε ότι
        // η συμβολοσειρά είναι μέσα στο λεξικό μας.
        cout << "YES" << endl;
    }
}