Suffix Trie Construction

• Time : O(n^2) populateSuffixTrieFrom | O(n) contains
• Space : O(^2)

c++

#include <unordered_map>
using namespace std;

// Do not edit the class below except for the
// populateSuffixTrieFrom and contains methods.
// Feel free to add new properties and methods
// to the class.
class TrieNode {
public:
    unordered_map<char, TrieNode *> children;
};

class SuffixTrie {
    void insert(string& s, int p) {
        auto *node = root;
        while(p < s.length()) {
            if(!node->children.count(s[p]))
                node->children[s[p]] = new TrieNode();
            node = node->children[s[p++]];
        }
        if(!node->children.count(endSymbol))
            node->children[endSymbol] = nullptr;
    }
public:
    TrieNode *root;
    char endSymbol;

    SuffixTrie(string str) {
        this->root = new TrieNode();
        this->endSymbol = '*';
        this->populateSuffixTrieFrom(str);
    }

    void populateSuffixTrieFrom(string str) {
        for(int i = 0; i < str.length(); i++) {
            insert(str, i);
					cout<<root->children.size()<<endl;
        }
    }

    bool contains(string str) {
        auto *node = root;
        for(int i = 0; i < str.length(); i++) {
            if(!node->children.count(str[i])) return false;
            node = node->children[str[i]];
        }
        return node->children.count(endSymbol);
    }
};