Question

We say that the string x = x₁x₂ ... x_n is a subsequence of the string y = y_1y2 ... y_m in the usual way: and there are indices $1\leq i_{1} < i_{2} < ... i_{n} \leq m$ such that, $(\forall k)x_{k} = y_{i_k}$ . The goal is a greedy strategy to test in O(n+m) time whether x is a subsequence of y (no code is required)

1 < 1

(a) Describe the greedy choice

(b) Justify the correctness of your greedy choice.

Answer 1

X can be non contigous subsequence of Y if all the characters of X appears in Y and in that order.

Below is the C++ code I hope that i have provided sufficient comments for your better understanding

#include <bits/stdc++.h>
using namespace std;
int main()
{
string s,t;
int len1,len2,i,j;

//Take input from user
cout<<"Enter 1st string : ";
cin>>s;
cout<<"Enter 2nd string : ";
cin>>t;

//store length of both the strings
len1=s.size();
len2=t.size();

//i will keep track of current index for string s
//j will keep track of current index for string t
i=0;j=0;
while(i<len1&&j<len2)
{
//character in "t" is matched with "s"
//move forward in "t" to check for its next character
//move forward by incrementing "j"
if(s[i]==t[j])
{
j++;
}
//move forward in s whether character is matched or not
i++;
}

//We reached end of string "t"
//means all the characters are found in "s"
if(j==len2)
{
cout<<t<<" is non contigous substring of "<<s;
}
else
{
cout<<t<<" is not non contigous substring of "<<s;
}
return 0;
}

Below is the screenshot of output-

Here since both the strings are to be travelled atmost once and the strings are of length m and n hence time complexity =O (m+n)

b) Since we are travelling both the strings without skipping any character hence we will always obtain the correct solution that is whether the string is a subsequence of other string or not.

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.