Find Pattern in String

Posted: 28 Jan, 2021
Difficulty: Easy


Try Problem

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.

1. There may be more than one occurrence of 'P' in 'S'.
2. Some alphabets in the strings may be repeated.
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.


You don’t have to print anything, it has already been taken care of. Just implement the given function. 
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.
Approach 1

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).
Try Problem