SuffixTrie

#include <iostream>
#include <vector>

const int ALPHABET_SIZE = 26;

// Trie node
struct TrieNode
{
    TrieNode * children[ALPHABET_SIZE];
    bool isEndOfWord;
};

// Returns new trie node (initialized to NULLs)
TrieNode *getNode(void)
{
    struct TrieNode *pNode =  new TrieNode;

    pNode->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
    {
        pNode->children[i] = NULL;
    }
    return pNode;
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(TrieNode *root, std::string key)
{
    TrieNode *pCrawl = root;

    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();

        pCrawl = pCrawl->children[index];
    }
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}

std::string findSubstringInWord(std::string word, TrieNode * root)
{
    int lenLongSubstr = 0;
    int longestPos = 0;
    int length = 0;

    for (int i=0; i<word.length(); ++i)
    {
        TrieNode *pCrawl = root;

        for (int j=i; j<word.length(); ++j)
        {
            int index = word[j] - 'a';
            if (!pCrawl->children[index])
                break;
            pCrawl = pCrawl->children[index];
            length = j - i + 1;
            if (pCrawl->isEndOfWord && length>lenLongSubstr)
            {
                lenLongSubstr = length;
                longestPos = i;
            }
        }
    }

    if (lenLongSubstr==0)
    {
        return word;
    }
    else
    {
        word.insert(longestPos, "[");
        word.insert(longestPos + lenLongSubstr + 1, "]");
        return word;
    }
}

std::vector<std::string> findSubstrings(std::vector<std::string> words, std::vector<std::string> parts)
{
}

// driver program to test above functions
int main()
{
    //vector<string> words = {"Apple", "Melon", "Orange", "Watermelon"};
    //vector<string> parts = {"a", "mel", "lon", "el", "An", "ter"};
    //vector<string> words = {"Watermelon"};
    //vector<string> parts = {"a", "mel", "el"};

    //std::vector<std::string> result = findSubstrings(words, parts);
    //for (std::vector<std::string>::iterator it = result.begin(); it!=result.end(); ++it)
    //{
    //    cout << "  " << *it;
    //}

    std::string word = "watermelon";
    std::string part = "ter";

    TrieNode *root = getNode();
    insert(root, part);

    std::cout << findSubstringInWord(word, root);

    return 0;
}