# UVa 10860

## Summary

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

You can create the explicit graph in ${\displaystyle O(n^{2}m)}$ (where ${\displaystyle n}$ is the length of the longer string, and ${\displaystyle m}$ 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 ${\displaystyle O(n^{2}m)}$ as that is the amount of data we're given.

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

## Output

```Set 1: 5.
Set 2: Not possible.
```