{"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 – Given two strings, find if first string is a subsequence of second"},"content":{"rendered":"

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

Examples:<\/strong><\/p>\n

Input: str1 = “AXY”, str2 = “ADXCPY”
\nOutput: True (str1 is a subsequence of str2)<\/p>\n

Input: str1 = “AXY”, str2 = “YADXCP”
\nOutput: False (str1 is not a subsequence of str2)<\/p>\n

Input: str1 = “gksrek”, str2 = “geeksforgeeks”
\nOutput: True (str1 is a subsequence of str2)<\/p>\n

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

Following is Recursive Implementation<\/strong><\/p>\n

C Program<\/span> <\/div> 
\/\/ Recursive C++ program to check if a string is subsequence of another string#include<iostream>#include<cstring>using namespace std; \/\/ Returns true if str1[] is a subsequence of str2[]. m is\/\/ length of str1 and n is length of str2bool isSubSequence(char str1[], char str2[], int m, int n){    \/\/ Base Cases    if (m == 0) return true;    if (n == 0) return false;     \/\/ If last characters of two strings are matching    if (str1[m-1] == str2[n-1])        return isSubSequence(str1, str2, m-1, n-1);     \/\/ If last characters are not matching    return isSubSequence(str1, str2, m, n-1);} \/\/ Driver program to test methods of graph classint main(){    char str1[] = "gksrek";    char str2[] = "geeksforgeeks";    int m = strlen(str1);    int n = strlen(str2);    isSubSequence(str1, str2, m, n)? cout << "Yes ":                                     cout << "No";    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
Yes<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
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}]}}