4. Consider the following problem. The input is a target string T of length n

and a set of words W = {₁,...,} of total length L (i.e., if | denotes the

length of word w, then L =

as a sequence of words from W.

-1

₁|w₂]). We want to know if T can be written

For example, the target string T-abbababa with W = {abba, ab, aba, bab} can

be written as ab+bab+aba. But the target string T-abbaba cannot be written

in such a way. (These two examples have m=4, L=12, and n = 8 for the first

one and n = 6 for the second one.)

Show an algorithm that decides in polynomial time whether T can or cannot

be written as a sequence of words from W. Hlint: Try a dynamic programming

approach.

Also state the worst-case running time of your algorithm as a function of n, m

and/or L.