Rabin Carp

Posted: 4 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a string ‘str’ of length 'N' and a string ‘pat’ of length 'M'. Your task is to find the starting index of all the occurrences of ‘pat’ in str.

You need to return a list of integers that denote the indices from which ‘pat’ is present in ‘str’(consider 0 based indexing).

For example,

Let str= “AABAACAADAABAABA”

And pat= “AABA”

We will return the array/list [0,9,12] as we can clearly see that from indices 0 9 and 12 we have the same pattern ‘pat’ in ‘str’

Note

1. 'str' and 'pat' will consist of only uppercase English letters.
2. Two occurrences of a pattern may overlap with each other. For example, for str = "AAAA" and pat = "AA", you need to return [0,1,2] and not [0,2].
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains the string ‘str’.
The second line of each test case contains the string ‘pat’        
Output Format
For each test case, return a list of integers denoting the indices where the match happens.
If no match happens, return an empty array.
Output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 5000
1 <= M <= 5000
1<= M <= N
'str' and 'pat' will consist of only uppercase english letters.


Where ‘T’ is the total number of test cases, N is the length of 'str' and 'M' is the length of 'pat'. 
Time limit: 1 second
Approach 1

The key idea in solving this problem using this approach is that we can naively search for pattern ‘ptr’ in ‘str’ by simply iterating through the ‘str’. If we find a match we add the current index in our array/list ‘result’.

      The algorithm will be -

  • We start iterating from the start of the string ‘str’ to (size of ‘str’ - size of ‘pat’) to check for a match.
  • In each iteration, we define a variable ‘j’ which and take a loop from ‘i’ to ‘i+ size of ‘pat’) to match the pattern string with the current string from index ‘i’. If the current substring from index ‘i’ matches the pat string, we add ‘i’ to our array/list ‘result’.
  • Finally, we return the array/list ‘result’.
Try Problem