A string S over an alphabet set E is a concatenation of some symbols from E. For example, if E = {a, b, c} then both abcabca and cbabbba are strings over E.

String B is a substring over S if B can be obtained by deleting one or more symbols from S. For example B = cab is a substring of String S = cabbabababa.

Design a greedy algorithm in such a manner that given string S and substring T on the alphabet set E and show the following with justification:

1. decides if B is a substring of S and outputs a yes or no according to the condition

2. if B is a substring of S then determine which symbols must be deleted from S to make it B

3. Why does this algorithm run in O(m+n) time? Justify.

Algorithm can be described using a simple pseudocode-based approach.

Also prove after developing the algorithm that:

1. If algorithm's output is "yes" then B is a substring of S

2. If B is a substring of S then the algorithm will output "yes"