Search Pattern (Rabin-Karp Algorithm)

Moderate

0/80

Average time to solve is 20m

Contributed by

72 upvotes

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

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

cxyzghxyzvjkxyz
xyz

Sample Output 1:

3
2 7 13

Explanation Of Sample Input 1 :

The pattern ‘pattern’ = “xyz” appears at 3 positions in ‘text’.

Sample Input 2 :

ababacabab
aba

Sample Output 2 :

3
1 3 7

Explanation Of Sample Input 2 :

Here we have an overlap between the first occurrence (at position 1) and the second occurrence (at position 3), and we are considering both.

Sample Input 3 :

abcd
xy

Sample Output 3 :

Expected time complexity:

The expected time complexity is O(‘n’ + ‘m’).

Constraints:

1 <= ‘n’ <= 10^5
1 <= ‘m’ <= ‘n’

Console