# Find Pattern in String

Posted: 28 Jan, 2021
Difficulty: Easy

## 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.
``````
##### 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).