Find all occurrences of multiple patterns

The idea is to iterate through all the elements of the array 'ARR' and for each element of the array, traverse through the string 'S' and find all the occurrences of that element as substrings. 

Steps:

1. Let ‘ANS’ be an array of arrays  having 'N' elements. We will use ANS[i], to store indexes of all the occurences of ARR[i] in the string S. 
2. Iterate from ‘i’ = 0 to ‘N’ - 1 
   • Iterate from j = 0 to S.length()-ARR[i].length()
     • If the substring of string S starting at index j  and having length equal to length of ARR[i], is equal to ARR[i], then we will add the index j to array ANS[i]. As we have found an occurence of the string ARR[i] in the string S. 
3. Return the array ‘ANS’. 

The idea is to build a suffix tree for the string S to solve the problem. Suffix tree of a string is a Trie that is built by inserting all the suffixes of the string in it. The advantage of building a suffix tree is that all the substrings of the string S will be present in the built Suffix Tree as a prefix using which we can easily and efficiently find all the indices of occurrences of all the strings. All nodes of the built trie will contain pointers to all its children nodes and an array containing indices of the suffixes passing through that node.

After building the suffix tree, we will iterate through all the elements of the array, and for each array element, we will search it in the built Trie. The node corresponding to the last character of the array element contains the index of all the substring occurrences of that element. In case we are not able to find an element in the trie, this means that no occurrence of that element is present in the String S.

The structure of the trie class will be :

class TrieNode
{
public:
    TrieNode *children[26];
    vector<int> index;
    TrieNode()
    {
        for (int i = 0; i < 26; i++)
        {
            children[i] = NULL;
        }
    }
    ~TrieNode()
    {
        for (int i = 0; i < 26; i++)
        {
            if (children[i] != NULL)
            {
                delete children[i];
            }
        }
        index.clear();
        index.resize(0);
    }
};

The array “CHILDREN” stores the pointers to the children nodes of the current node. 

Steps: 

1. Make an empty trie. Let ‘ROOT’ be it's root.
2. Iterate from ‘i’ = 0 to S.length()
   • Insert the suffix starting at index ‘i’ into the trie.
3. Let ‘ANS’ be an array of arrays  having 'N' elements. We will use ANS[i], to store indexes of all the occurences of ARR[i] in the string ‘S’. 
4. Iterate from ‘j’ = 0 to ‘N’ - 1 
   • Search for the string ARR[i] in the built trie.
   • If ARR[i] is not present in the trie, then we will set ANS[i] as an empty array.
   • Otherwise, let 'LAST_NODE' be a trie node that corresponds to the last character of the string ARR[i].
     • Add all the indices  of all strings present in the trie which pass through the 'LAST_NODE'. 
     • Sort the array ANS[i].