Shortest Common Superstring algorithm?

Question

I'm trying to code this problem here:

but I'd like to find an algorithm that breaks down the steps for solving the problem. I can't seem to find anything too useful online so I've come here to ask if anyone knows of a resource which I can use to refer to an algorithm that solves this problem.

Answer 1

This is called the shortest common supersequence problem. The idea is that in order for the supersequence to be the shortest, we want to find as many shared bits of a and b as possible. We can solve the problem in two steps:

1. Find the longest common subsequence of a and b.

2. Insert the remaining bits of a and b while preserving the order of these bits.

We can solve the longest common subsequence problem using dynamic programming.