Find Pattern in String

Posted: 28 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

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.

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

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