Find all occurrences of multiple patterns

Posted: 8 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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
Approach 1

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 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’. 
Try Problem