Find Pattern in String - KMP Algorithm

Easy
0/40
Average time to solve is 10m
profile
Contributed by
43 upvotes
Asked in companies
OracleWalmartMicrosoft

Problem statement

You are given two strings 'S' and 'P' consisting of lowercase English alphabets. Your task is to find whether the 'P' is present in 'S' as a substring or not.

Note 
1. There may be more than one occurrence of 'P' in 'S'.
2. Some alphabets in the strings may be repeated.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer 'T', representing the number of test cases

Then the 'T' test cases follow.

The first line of each test case contains two space-separated strings 'P' and 'S' respectively.
Output Format: 
For each test case, print a single line containing “YES” if string 'P' is present in string 'S' as a substring, otherwise print “NO”.

The output for each test case will be printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= |S| <= 10000
1 <= |P| < |S|

Where |S| and |P| represents the length of the string 'S' and 'P' respectively.

Time limit: 1 sec.

Sample input 1:

3
xxy yxxyxxy
a baac
cfg cgfgfc

Sample output 1

YES
YES
NO

Explanation for sample output 1

In the first test case, there are two substrings equal to P on index 1 and 4 in S.

In the second test case, there are two substrings equal to P on indexes 1 and 2 in S.
In the third test case, P does not exist in S.

Sample input 2:

3
bbb abba
iqw hdhhdqoa
car caribbean

Sample output 2

NO
NO
YES

Explanation for sample output 2

 In the first test case, P does not exist in S.
 In the second test case, P does not exist in S.
 In the third test case, there is one substring equal to P on index 1 in S.
Hint

Can we check all possible substrings to find the pattern?

Approaches (2)
Brute Force

The idea is to generate all the substrings of ‘S’ of size equal to the size of ‘P’ and match each of them with the ‘P’.

 

  • Let ‘M’ is the size of ‘P’ and ‘N’ is the size of ‘S’.
  • Iterate over S[i] for each 0 <= i <= N - M and do:
    • Iterate over P[j] for each 0 <= j < M and do:
      • If P[j] == S[i+j] then do:
        • Continue iterating
      • If P[j] is not equal to S[j] then do:
        • Exit from the inner loop.
    • If j == i + M then it means we have matched the substring with P so:
      • Return TRUE
  • Return FALSE(if we still have not matched a substring).
Time Complexity

O((N - M) * M), where ‘M’ is the length of the ‘P’ and ‘N’ is the length of ‘S’.

 

As we are iterating the first N - M characters of the string ‘S’, and for each character at position j we are running a loop from j to j + M, to check for the existence of pattern ‘P’.

Space Complexity

O(1).

 

As we are using constant extra memory.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Find Pattern in String - KMP Algorithm
Full screen
Console