 New update is available. Click here to update.
Last Updated: 4 Feb, 2021
##### Search Pattern (Rabin-Karp Algorithm)
Moderate
Problem statement #### For each occurrence, print the index from where it starts in the string ‘text’ (1 - indexed).

##### Example:
``````Input: ‘text’ = “cxyzghxyzvjkxyz” and ‘pattern’ = “xyz”

Output: 2 7 13

Explanation: The pattern ‘pattern’ = “xyz” appears at 3 positions in ‘text’.
``````
##### Input Format:
``````The first line contains the string ‘text’.
The second line contains the string ‘pattern’.
``````

##### Output format:
``````The first line contains an integer ‘count’, the number of occurrences.
The first line contains ‘count’ integers, the positions of occurrence of ‘pattern’ in ‘text’ in sorted order.
``````

##### Note:
``````You need not print anything. Return the list of positions in any order. They will be sorted and printed.
`````` Approaches

## 01Approach Check each substring in ‘text’ of length ‘m’ and see if they are equal to ‘pattern’.

If we find a match we add the current index (1 - based) in our list ‘ans’.

The steps are as follows:

List stringMatch(string ‘text’, string ‘pattern’)

1. Let ‘n’ = ‘text.length’, ‘m’ = ‘pattern.length’
2. Let ‘ans’ be a list storing the indices of occurrences.
3. For ‘i’ in the range from 0 to ‘n’ - ‘m’ (inclusive):
• Check whether the substring of ‘text’ from index ‘i’ to ‘i’ + ‘m’ is equal to ‘pattern’ or not.
• If the substring is equal to ‘pattern’:
• Add ‘i’ + 1 in ‘ans’.
4. Return ‘ans’. 