Update appNew update is available. Click here to update.
Last Updated: 4 Feb, 2021
Search Pattern (Rabin-Karp Algorithm)
Moderate
Problem statement

You’re given two strings, 'text' of length 'n' and 'pattern' of length 'm', consisting of lowercase characters.


Find all the occurrences of the string ‘pattern’ in ‘text’.


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