Find Pattern in String - KMP Algorithm

Easy

0/40

Average time to solve is 10m

Contributed by

32 upvotes

+5 more companies

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.

Console