If S and T are strings, we say that S is a subsequence of T if all the letters of S appear in T in the same relative order that they appear in S. For example, pin is a subsequence of the programming, and the string singe is a subsequence of springtime. However, steal is not a subsequence of least, since the letters are in the wrong order, and p is not a subsequence of team because there is no p in team.

Note that the empty string () is a subsequence of every string.

A. Write a function named hasSubsequence that given two strings returns a Boolean to represent whether the second string is a subsequence of the first. Your solution must be recursive and must use the following function prototype:

bool hasSubsequence(const string& T, const string& S);

Note: This problem has a beautiful recursive decomposition. Think about the following questions: What strings are subsequences of an empty string?

What happens if the first character of the parameter S matches the first character of the parameter T? What happens if it doesn't? You can assume that the strings are case-sensitive, so the word AGREE is not a subsequence of the word agreeable.

B. Calculate the time complexity of hasSubsequence. (answers.pdf)

C. Write a main function that calls and tests hasSubsequence.

PROGRAMMING LANGUAGE: C++