{"id":1550,"date":"2020-06-11T09:46:11","date_gmt":"2020-06-11T09:46:11","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1550"},"modified":"2022-03-21T11:32:10","modified_gmt":"2022-03-21T11:32:10","slug":"find-substring","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-substring\/","title":{"rendered":"Find Substring"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For given two strings A<\/code> and B<\/code>, print out if B<\/code> is a substring of A<\/code> or not. If yes print YES<\/code>, else print NO<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h3>\n
Input:\n1\nexpertcoder coder\nzenith cod\n\nOutput:\nYES\nNO\n\nExplanation:\nCase-1:\n'coder' is found at index 6 in the given string 'expertcoder'. So we print YES.\n\nCase-2:\n'cod' does not exist in given substring 'zenith'. So we print NO.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
\n
Substring<\/strong>: A substring of a string is part of the string. For example, prep<\/code> exists in prepbytes<\/code>, so prep<\/code> is a substring of prepbytes<\/code>.<\/p>\n
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.
\n2) If B<\/code>‘s length is greater than A<\/code>‘s length, it can’t be it’s substring, as a substring is a part of the string. B<\/code>‘s length always will be smaller than A<\/code>‘s length.
\n3) We iterate over each element of A<\/code> and then check if string starting from current element to (CurrentIndex + len(B))th<\/sup> element is same as our substring or not. If not we move to the next element else print YES<\/code> and finish the process. If no such string is found after all iterations, we print NO<\/code>.
\n4) Note:<\/em><\/strong> We check all elements only up to (len(A) – len(B))th<\/sup> element of A<\/code>, as string starting from this element to last element of string A<\/code> will always be shorter than our string B<\/code>. So that way B<\/code> can never be those strings.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
    \n
  • Lets assume string S<\/code> is 'expertcoder'<\/code> and substring to find T<\/code> is 'ertco'<\/code>.  <\/li>\n
  • We start from starting index of string S<\/code>, and check if current character matches starting index of string T<\/code>.<\/li>\n
  • If No, we move to next character in string S<\/code>, else we check until whole pattern string T<\/code> matches to string starting from current index.<\/li>\n
  • If we find the substring T<\/code> in S<\/code>, we print YES<\/code> and if we reach end of string S<\/code>, we print No<\/code>.<\/li>\n
  • We can understand using the following pictorial representation for above example.<\/li>\n<\/ul>\n<\/blockquote>\n
    \"\"<\/p>\n
    \n
      \n
    • Here we can see at index 3<\/code> of string S<\/code>, we found the substring T<\/code>, so we print YES<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n
      Solutions<\/h3>\n
      \t\t\t\t\t\t