Longest prefix matching - trie

/***

Longest prefix matching

Given a dictionary of words and an input string,

find the longest prefix of the string which is also a word in dictionary.

Example:

Let the dictionary contains the following words:

{are, area, base, cat, cater, children, basement}

Below are some input/output examples:

--------------------------------------

Input String            Output

--------------------------------------

caterer                 cater

basemexy                base

child                   < Empty >

***/

#include<iostream>

#include<string>

using namespace std;

struct node {

       char val;

       node *next[26];

       bool isEnd;

       node(char ch) {

              val = ch;

              isEnd = false;

              for(int i = 0; i<26; i++) next[i] = nullptr;

       }     

};

class trie {

public:

       trie(string *dictionary, int size);

       void buildtrie();

       node** gettrie();

       ~trie() { }

private:

       node *root[26];

       int sz;

       string *dic;

};

trie :: trie(string *dictionary, int size) {

       dic = dictionary;

       sz = size;

       for (int i = 0; i<26; i++) root[i] = nullptr;

}

void trie :: buildtrie() {

       //if(dic == nullptr) return;

       node **temp;

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

              temp = root;

              for(int j = 0; j<dic[i].size(); j++) {

                     if(temp[dic[i][j] - 'a'] == nullptr) {

                           temp[dic[i][j] - 'a'] = new node(dic[i][j]);   

                     }

                     if (j == dic[i].size()-1)

                           temp[dic[i][j] - 'a']->isEnd = true;

                     temp = temp[dic[i][j] - 'a']->next;                   

              }

       }     

}

node ** trie :: gettrie() {

       return root;

}

string getlongestprefix(string str, node **root) {

       node **temp = root;

       string out, st;

       if (str == "") return str;

       int i = 0;

       while (temp[str[i] - 'a'] != nullptr)

       {

              st.push_back(str[i]);

              if (temp[str[i] - 'a']->isEnd) out = st;

              temp = temp[str[i] - 'a']->next;

              i++;

       }

       return out;

}

void main() {

       string dic[] = {"are","base", "area",  "cat", "cater", "children", "basement"};

       int sz = sizeof(dic) / sizeof(string);

       string str = "basementxy";

       node** root;

       trie mytrie(dic, sz);

       mytrie.buildtrie();

       root = mytrie.gettrie();

      

       cout << getlongestprefix(str, root)<<endl;

}