UVa 10860

From Algorithmist
Jump to navigation Jump to search

10860 - Many a Little makes a Mickle[edit]

Summary[edit]

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.

Explanation[edit]

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.

Input[edit]

2
aabbabbabbbb
3
a
bb
abb
ewu**bbacsecsc
4
ewu
bba
cse
csc

Output[edit]

Set 1: 5.
Set 2: Not possible.