Find all occurrences of multiple patterns

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
MicrosoftIncedo Inc.

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
aa ab b
abaab
2
cc ty
acty
Sample Output 1:
2
0 3
1 4

2
Explanation for Sample Input 1:
For the first test case : 
The substring "aa" is present at 2nd index of the String "abaab". The substring "ab" is present at index 0 and index 3 of string S and the substring "b" is present at index 1 and index 4 of string S.

For the second test case:
The substring "cc" is not present in String S and the substring "ty" is present at index 2 of string S.
Sample Input 2:
2
3
cc aa bb
aabbccaa
3
p q r 
prrp
Sample Output 2:
4 
0 6 
2 

0 3 

1 2
Hint

Iterate through all elements of the array, and for each string try to find all the occurrences of it in the String S.

Approaches (2)
Brute Force Approach

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’. 
Time Complexity

O(N*|S|*|ARR[i]|), where ‘N’ is the number of elements in the array 'ARR', |S| denotes the length of the String 'S', and |ARR[i]| denotes the length of the  'i'th' element of the array 'ARR'.

 

As we are iterating through all the ‘N’ array elements, and for each array element, we are iterating through the String ‘S’ and checking all its substrings having length equal to that array element. Hence, the overall time complexity is O(N*|S|*|ARR[i]|).

Space Complexity

O(1).

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Find all occurrences of multiple patterns
Full screen
Console