The longest common subsequence (LCS) of two sequences T and P is the longest sequence L such that L is a subsequence of both T and P. The shortest common super sequence (SCS) of T and P is the smallest sequence L such that both T and P are a subsequence of L.
(a) Give efficient algorithms to find the LCS and SCS of two given sequences.
(b) Let d(T,P) be the minimum edit distance between T and P when no substitutions are allowed (i.e., the only changes are character insertion and deletion). Prove that d(T,P) = |SCS(T,P)|-|LCS(T,P)| where |SCS(T,P)| (|LCS(T,P)|) is the size of the shortest SCS (longest LCS) of T and P.