Shortest Common Supersequence Length
mediumDynamic Programming II+20 XPTime limit 3s
Two DNA fragments a and b must both be found inside one longer strand as subsequences (their letters appear in order, not necessarily next to each other). What is the length of the shortest strand that contains both?
Input: two lines: the strings a and b.
Output: the length of the shortest common supersequence.
Constraints: 1 ≤ length of a, b ≤ 1000; lowercase letters.
Example: for abac and cab, cabac works, so the answer is 5.
Think about it: letters shared by both strings can be written once if they line up in order — the most you can share is their longest common subsequence. So the answer is |a| + |b| − LCS(a, b), with the O(|a| · |b|) LCS table.
Sample input 1
abac cab
Sample output 1
5
Sample input 2
geek eke
Sample output 2
5
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).