Data-Structures-and-Algorithms-Notebook/Trees/Trie/Trie.cpp at master · KhanShaheb34/Data-Structures-and-Algorithms-Notebook · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

#define ALPHASIZE 26

struct node {
    bool endmark;
    node* next[ALPHASIZE + 1];
    node() {
        endmark = false;
        for(int i=0; i<ALPHASIZE; i++)
            next[i] = NULL;
    }
} *root;

void insertNode(string a){
    node* curr = root;
    for(int i=0; i<a.size(); i++) {
        int id = a[i] - 'a';
        if(curr->next[id] == NULL)
            curr->next[id] = new node();
        curr = curr->next[id];
    }
    curr -> endmark = true;
}

bool query(string a) {
    node* curr = root;
    for(int i=0; i<a.size(); i++) {
        int id = a[i] - 'a';
        if(curr->next[id] == NULL)
            return false;
        curr = curr->next[id];
    }
    return curr -> endmark;
}

int main() {
    root = new node();
    insertNode("hello");
    insertNode("world");
    insertNode("hell");
    insertNode("love");
    insertNode("lover");
    while(1){
        string q;
        cin>>q;
        if(query(q)) printf("Found");
        else printf("Not Found");
    }
    return 0;
}