Concepts Used

Strings

Difficulty Level

Easy

Problem Statement (Simplified):

For given two strings A and B, print out if B is a substring of A or not. If yes print YES, else print NO.

See original problem statement here

Test Case

Input:
1
expertcoder coder
zenith cod

Output:
YES
NO

Explanation:
Case-1:
'coder' is found at index 6 in the given string 'expertcoder'. So we print YES.

Case-2:
'cod' does not exist in given substring 'zenith'. So we print NO.

Solving Approach :

Substring: A substring of a string is part of the string. For example, prep exists in prepbytes, so prep is a substring of prepbytes.

1) To check if two strings are the same or not, we check their respective elements one by one if all elements are the same at the corresponding index, they both are the same.
2) If B‘s length is greater than A‘s length, it can’t be it’s substring, as a substring is a part of the string. B‘s length always will be smaller than A‘s length.
3) We iterate over each element of A and then check if string starting from current element to (CurrentIndex + len(B))th element is same as our substring or not. If not we move to the next element else print YES and finish the process. If no such string is found after all iterations, we print NO according to the algorithms for beginners.
4) Note: We check all elements only up to (len(A) – len(B))th element of A, as string starting from this element to last element of string A will always be shorter than our string B. So that way B can never be those strings.

Example

  • Lets assume string S is 'expertcoder' and substring to find T is 'ertco'.
  • We start from starting index of string S, and check if current character matches starting index of string T.
  • If No, we move to next character in string S, else we check until whole pattern string T matches to string starting from current index.
  • If we find the substring T in S, we print YES and if we reach end of string S, we print No.
  • We can understand using the following pictorial representation for above example.
  • Here we can see at index 3 of string S, we found the substring T, so we print YES.

Solutions

 #include <stdio.h>

    int main()
    {
      int test;
      scanf("%d", &test);

      while(test--){

        char a[1001], b[1001];
        scanf("%s%s", a,b);

        int found = 0;

        if(strlen(a)>=strlen(b)){

            for(int i=0; i<=strlen(a)-strlen(b) && !found; i++){

              found = 1;

              for(int j = 0; j<strlen(b); j++){

                  if( a[i+j] != b[j] ){
                      found = 0;
                      break;
                  }

                }
            }
        }

        if(found == 1)
            printf("YES\n");
        else
            printf("NO\n");


      }

      return 0;
    }
 #include <bits/stdc++.h>
    using namespace std;

    int main()
    {
      int test;
      cin>>test;

      while(test--){

        char a[1001], b[1001];
        cin>>a>>b;

        bool found = false;

        if(strlen(a)>=strlen(b)){

            for(int i=0; i<=strlen(a)-strlen(b) && !found; i++){

              found = true;

              for(int j = 0; j<strlen(b); j++){

                  if( a[i+j] != b[j] ){
                      found = false;
                      break;
                  }

                }
            }
        }

        if(found)
            cout<<"YES\n";
        else
            cout<<"NO\n";


      }

      return 0;
    }


import java.util.*;
    import java.io.*;
    import java.lang.Math;

    public class Main {
      public static void main(String args[]) throws IOException {

        Scanner sc= new Scanner(System.in);
        int test = sc.nextInt();
          while(test != 0){

            String a = sc.next();
            String b = sc.next();

            int found = 0;

            if(a.length()>=b.length()){

                for(int i=0; i<=a.length()-b.length() && found == 0; i++){

                  found = 1;

                  for(int j = 0; j<b.length(); j++){

                      if( a.charAt(i+j) != b.charAt(j) ){
                          found = 0;
                          break;
                      }

                    }
                }
            }

            if(found == 1)
                System.out.println("YES");
            else
                System.out.println("NO");


            test--;
          }

      }
    }



Space Complexity

O(1)

Previous post Number of Substrings Containing All Three Characters
Next post Prime Numbers

Leave a Reply

Your email address will not be published. Required fields are marked *