3. Tired of solving the longest common subsequence problem so many times, Gabriel yearns to do something different. Now, when given two strings S and T, he wants to find the shortest com- mon supersequence. That is, he wants to find a shortest (maybe not unique!) possible string SCS(S, T) (a shortest common supersequence) such that S and T are both subsequences of SCS(S, T). For example, one such shortest common supersequence of "Turing and Church" is "TChurcinhg". Another example is SCS( "Seven", "evens") = "sevens". (a) Find all SCSs for "Bob" and "Tom" (b) Find an SCS for "Apple and "Microsoft (c Find all SCSs for "Homeowner" and meow (d) Given two strings S = 81s2 sm of length m and T-tit2 tn of length n as inputs, help Gabriel devise an algorithm that finds a shortest common supersequence of S and T in O(mn) time. Show that your algorithm indeed terminates in O(mn) time