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 I 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 = 81828m of length m and T = ttt 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.