Search Pattern (KMP - Algorithm)

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes
Asked in companies
AmazonAdobeIBM

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: Occurrences = [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 :
0


Expected time complexity:
The expected time complexity is O(n + m).


Constraints:
1 <= ‘n’ <= 10 ^ 5
1 <= ‘m’ <= ‘n’
Approaches (2)
Brute Force

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

O((n - m) * m), Where ‘n’ and ‘m’ are the lengths of ‘text’ and ‘pattern’ respectively.

The outer loop ‘i’ is running ‘n’ - ‘m’ + 1 times and each inner loop is running ‘m’ times.

Therefore total execution time = (n - m + 1) * m.

Hence the time complexity is O((n - m) * m).

Space Complexity

O(1)

We are using constant auxiliary space. The only space we are using is to store the positions of matching occurrences in ‘ans’.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Search Pattern (KMP - Algorithm)
Full screen
Console