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β.