{"id":26963,"date":"2018-01-05T21:01:32","date_gmt":"2018-01-05T15:31:32","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26963"},"modified":"2018-01-05T21:01:32","modified_gmt":"2018-01-05T15:31:32","slug":"c-programming-given-two-strings-find-first-string-sub-sequence-second","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-given-two-strings-find-first-string-sub-sequence-second\/","title":{"rendered":"C Programming &#8211; Given two strings, find if first string is a subsequence of second"},"content":{"rendered":"<p>Given two strings str1 and str2, find if str1 is a subsequence of str2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements (source: wiki). Expected time complexity is linear.<\/p>\n<p><strong>Examples:<\/strong><\/p>\n<p>Input: str1 = \u201cAXY\u201d, str2 = \u201cADXCPY\u201d<br \/>\nOutput: True (str1 is a subsequence of str2)<\/p>\n<p>Input: str1 = \u201cAXY\u201d, str2 = \u201cYADXCP\u201d<br \/>\nOutput: False (str1 is not a subsequence of str2)<\/p>\n<p>Input: str1 = \u201cgksrek\u201d, str2 = \u201cgeeksforgeeks\u201d<br \/>\nOutput: True (str1 is a subsequence of str2)<\/p>\n<p>The idea is simple, we traverse both strings from one side to other side (say from rightmost character to leftmost). If we find a matching character, we move ahead in both strings. Otherwise we move ahead only in str2.<\/p>\n<p>Following is <strong>Recursive Implementation<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Recursive%20C%2B%2B%20program%20to%20check%20if%20a%20string%20is%20subsequence%20of%20another%20string%0A%23include%3Ciostream%3E%0A%23include%3Ccstring%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20true%20if%20str1%5B%5D%20is%20a%20subsequence%20of%20str2%5B%5D.%20m%20is%0A%2F%2F%20length%20of%20str1%20and%20n%20is%20length%20of%20str2%0Abool%20isSubSequence(char%20str1%5B%5D%2C%20char%20str2%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20Cases%0A%20%20%20%20if%20(m%20%3D%3D%200)%20return%20true%3B%0A%20%20%20%20if%20(n%20%3D%3D%200)%20return%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20last%20characters%20of%20two%20strings%20are%20matching%0A%20%20%20%20if%20(str1%5Bm-1%5D%20%3D%3D%20str2%5Bn-1%5D)%0A%20%20%20%20%20%20%20%20return%20isSubSequence(str1%2C%20str2%2C%20m-1%2C%20n-1)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20last%20characters%20are%20not%20matching%0A%20%20%20%20return%20isSubSequence(str1%2C%20str2%2C%20m%2C%20n-1)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%20of%20graph%20class%0Aint%20main()%0A%7B%0A%20%20%20%20char%20str1%5B%5D%20%3D%20%22gksrek%22%3B%0A%20%20%20%20char%20str2%5B%5D%20%3D%20%22geeksforgeeks%22%3B%0A%20%20%20%20int%20m%20%3D%20strlen(str1)%3B%0A%20%20%20%20int%20n%20%3D%20strlen(str2)%3B%0A%20%20%20%20isSubSequence(str1%2C%20str2%2C%20m%2C%20n)%3F%20cout%20%3C%3C%20%22Yes%20%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22No%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Yes<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Given two strings str1 and str2, find if str1 is a subsequence of str2. A subsequence is a sequence that can be derived from another sequence by deleting<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,69866,1],"tags":[75061,73170,73158,73394,76934,71496,76933,71145,78226,72834,74751,76930,76935,76929,75059,80456,76924,76938,75689,76923,73148,76928],"class_list":["post-26963","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","tag-c-programming-character","tag-c-programs-on-strings","tag-c-string-functions","tag-compare-strings-in-c","tag-copy-string-in-c","tag-dynamic-programming-algorithm","tag-how-to-input-a-string-in-c","tag-quicksort-c","tag-sequence-definition","tag-string-array-in-c","tag-string-compare-in-c","tag-string-functions-in-c","tag-string-functions-in-c-with-examples","tag-string-h-functions","tag-string-in-c-language","tag-string-length-in-c","tag-string-manipulation-functions-in-c","tag-string-manipulation-in-c","tag-string-operations-in-c","tag-string-programming","tag-string-programs-in-c","tag-write-a-program-to-accept-string-from-user"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26963","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26963"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26963\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26963"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26963"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}