10860 - Many a Little makes a Mickle
We can look at the space between the characters as a vertex, the characters are edges, and two vertices are connected if the string between them is located in given shorter strings (or the reverse). Then it's just standard Dynamic Programming or Shortest Path.
You can create the explicit graph in (where is the length of the longer string, and is the length of the shorter string), or a careful construction will allow you to use the graph implicitly at no penalty. The problem is strictly as that is the amount of data we're given.
2 aabbabbabbbb 3 a bb abb ewu**bbacsecsc 4 ewu bba cse csc
Set 1: 5. Set 2: Not possible.