# Find all occurrences of multiple patterns

#### You are given an array 'ARR' of strings having 'N' strings. You are also given a string 'S'. Your task is to find all the occurrences of each string of the array 'ARR' as substrings in the string 'S'.

#### For example:

```
Consider the array 'ARR' = { "ab", "aa" } and the string 'S' = "aabab".
The substring "ab" is present at index 1 and index 3 of the String 'S' and the substring "aa" is present at index 0 of the String S.
```

##### Input Format:

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains an integer 'N', denoting the number of elements in the array 'ARR'.
The second line of each test case contains 'N' space-separated strings denoting the elements of the array 'ARR'.
The third line of each test case contains the String 'S'.
```

##### Output Format:

```
For each test case, return a 2D array of N rows, the i'th of which contains all the indices of string at which 'ARR[i]' is present as substring.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given functions.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 100
1 <= |S| <= 100
1 <= |ARR[i]| <= 100
All input strings contain lowercase English alphabets only.
Time Limit: 1 sec
```

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:**

- 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.** - 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**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.**

- If the substring of string

- Iterate from
- 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: **

- Make an empty trie. Let ‘
**ROOT’**be it's root. - Iterate from ‘
**i’ = 0**to**S.length()**- Insert the suffix starting at index ‘
**i’**into the trie.

- Insert the suffix starting at index ‘
- 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’.** - 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]**.

- Add all the indices of all strings present in the trie which pass through the

- Search for the string