Find Pattern in String
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

Question

Find Pattern in String

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.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: OtherExplanation:

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

Java (SE 1.8)

/*

    Time complexity: O((N - M) * M)

    Space complexity: O(1)



    Where N is the length of string s and M is length of string p.

*/



public class Solution {

    public static boolean findPattern(String p, String s) {

        int m = p.length();

        int n = s.length();



        for (int i = 0; i <= n - m; i++) {



            int j;

            for (j = 0; j < m; j++) {

                if (p.charAt(j) == s.charAt(i + j)) {

                    continue;

                }

                // If there is a mismatch, we do not check furthur.

                else {

                    break;

                }

            }



            // If j is equal to m then it means p is present in s.

            if (j == m) {

                return true;

            }

        }



        return false;

    }

}

Python (3.5)

'''

    Time complexity: O((N - M) * M)

    Space complexity: O(1)



    Where N is the length of string s and M is length of string p.

'''



def findPattern(p:str, s:str):

    n = len(s)

    m = len(p)

    

    for i in range (n - m + 1):

        j = 0

        

        while j < m:

            

            if p[j] == s[i+j]:

                j+=1

                continue

            # If there is a mismatch, we do not check furthur.

            else:

                break

            

            j += 1

         

        # If j is equal to m then it means p is present in s.

        if j ==m:

            return True

    

    return False

C++ (g++ 5.4)

/*

    Time complexity: O((N - M) * M)

    Space complexity: O(1)



    Where N is the length of string s and M is length of string p.

*/



bool findPattern(string p, string s)

{

    int m = p.size();

    int n = s.size();

  

    for (int i = 0; i <= n - m; i++)

    {

        int j;



        for (j = 0; j < m; j++)

        {

            if (p[j] == s[i + j])

            {

                continue;

            }

            // If there is a mismatch, we do not check furthur.

            else

            {

                break;

            }



        }



        // If j is equal to m then it means p is present in s.

        if (j == m)

        {

            return true;

        }



    }

    

    return false;

}

Accepted Answer

KMP

The basic idea of KMP is to generate and use LPS array here LPS means longest proper prefix which is also a suffix. For example, if a string is ‘aada’ then :-

Proper prefixes are :[a, aa, aad]

Proper suffix are :[a,da,ada].

The LPS array helps us to skip characters while matching.

Basically this algorithm works in two parts where the first part is to generate the LPS array and the second part is to use this array to skip characters while matching P with S.

Part 1: Generate the LPS array.

Let ‘M’ is the size of ‘P’ and ‘N’ is the size of ‘S’.
Initialize an integer array LPS, initialized to zero.
Initialize an integer variable LEN=0 which is the length of the previous longest prefix suffix.
Initialize an integer variable IDX=0, to iterate over ‘P’.
Iterate while IDX
If P[IDX]==P[LEN] then do:
- Increase LEN by 1
- LPS[IDX]=LEN
- Increase IDX by 1
Else :
- If LEN is equal to zero then do:
  - LPS[IDX]=0
  - Increase IDX by 1.
- Else
  - LEN = LPS[IDX-1]

Part 2: Using the LPS array to find ‘P’ in ‘S’ :

Initialize an integer variable IDX1=0, to iterate over P.
Initialize an integer variable IDX2=0, to iterate over S.
Iterate while IDX2
If we found a match or P[IDX1] == S[IDX2] then do :
- Increase IDX1 by 1.
- Increase IDX2 by 1.
- If IDX2 == M then we can say we have found ‘P’ so do:
  - Return TRUE.
If IDX1 is less than N and P[IDX1] != S[IDX2](found mismatch) then do:
- If IDX2!=0 then do (Here comes the role of LPS we will simply skip LPS[IDX2-1] characters):
  - IDX2 = LPS[IDX2-1]
- Otherwise do :
  - Increase IDX1 by 1.

Return FALSE(if we still have not matched a substring).

Space Complexity: OtherExplanation:

O(M), where ‘M’ is the length of the ‘P’.

As we are using an array of size ‘M’ to store the LPS.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the string ‘S’.

Actually, the total time complexity will be O(N+M), where ‘M’ is the length of the string ‘P’, so we can simply say O(N) as ‘N’ will always be larger than 'M'.

Java (SE 1.8)

/*

    Time complexity: O(N)

    Space complexity: O(M)



    Where N is the length of string s and M is length of string p.

*/



// Function to get the LPS.

public class Solution {

    public static void getLps(String p, int[] lps) {



        int len = 0;

        int index = 1;

        int m = p.length();



        while (index < m) {



            if (p.charAt(index) == p.charAt(len)) {



                len += 1;

                lps[index] = len;

                index += 1;

            }

            else {

                if (len == 0) {

                    lps[index] = 0;

                    index += 1;

                }



                else {

                    // Skipping the characters.

                    len = lps[len - 1];

                }

            }

        }

    }



    public static boolean findPattern(String p, String s) {



        int m = p.length();

        int n = s.length();

        int[] lps = new int[m];



        for (int i = 0; i < m; i++) {

            lps[i] = 0;

        }



        getLps(p, lps);



        // We will use these indices to traverse in s and p.

        int index1 = 0;

        int index2 = 0;



        while (index1 < n) {



            if (s.charAt(index1) == p.charAt(index2)) {



                index2++;

                index1++;



                if (index2 == m) {

                    return true;

                }



                if (index1 == n) {

                    return false;

                }



            }

            else {

                if (index2 == 0) {

                    index1 += 1;

                }

                else {

                    // Skipping the characters.

                    index2 = lps[index2 - 1];

                }

            }

        }



        return false;

    }

}

Python (3.5)

'''

    Time complexity: O(N)

    Space complexity: O(M)



    Where N is the length of string s and M is length of string p.

'''



# Function to get the LPS.

def getLps(p, lps):

    

    l = 0

    index = 1

    m = len(p)

    

    while index < m:

        

        if p[index] == p[l]:

            l += 1

            lps[index] = l

            index += 1

        else:

            

            if l == 0:

                lps[index] = 0

                index += 1

            else:

                # Skipping characters.

                l = lps[l - 1]

                

    return lps



def findPattern(p:str, s:str):

    n = len(s)

    m = len(p)

    lps = [0] * m

    

    lps = getLps(p, lps)

    

    # We will use these indices to traverse in s and p.

    index1 = 0

    index2 = 0

    

    while index1 < n:

        

        if s[index1] == p[index2]:

            

            index1 += 1

            index2 += 1

            

            if index2 == m:

                return True

            

            if index1 == n:

                return False

        else:

            

            if index2 == 0:

                index1 += 1

            else:

                # Skipping the characters.

                index2 = lps[index2 - 1]

                

    return False

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(M)



    Where N is the length of string s and M is length of string p.

*/



// Function to get the LPS.

void getLps(string p, vector &lps) 

{

    int len = 0;

    int index = 1;

    int m = p.size();



    while (index < m)

    {

        if (p[index] == p[len])

        {

            len += 1;

            lps[index] = len;

            index += 1;

        }



        else

        {

            if (len == 0)

            {

                lps[index] = 0;

                index += 1;

            }



            else

            {

                // Skipping the characters.

                len = lps[len - 1]; 

            }

        }

    }

}



bool findPattern(string p, string s)

{

    int m = p.size();

    int n = s.size();

    vector lps(m, 0);



    getLps(p, lps);



    // We will use these indices to traverse in s and p.

    int index1 = 0;

    int index2 = 0;



    while (index1 < n)

    {

        if (s[index1] == p[index2])

        {

            index2++;

            index1++;

            if (index2 == m)

            {

                return true;

            }



            if (index1 == n)

            {

                return false;

            }

        }

        else

        {

            if (index2 == 0)

            {

                index1 += 1;

            }

            else

            {

                // Skipping the characters.

                index2 = lps[index2 - 1];

            }

        }

    }



    return false;

}

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

Input Format:

Output Format:

Note

Constraints:

Top Cisco Consultant Engineer interview questions & answers

Popular interview questions of Consultant Engineer

Top HR questions asked in Cisco Consultant Engineer