# Rabin Carp

Posted: 4 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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’.