Give the fastest, correct algorithm you can for solving the
composition problem.  Analyze your algorithm, stating and justifying
the complexity. onsider space as well as time.
    Let A = {a,b,c,…z}, the set of letters in the English alphabet.
Given an integer n, an array W[0,…,n-1] and a string y.  The array W
contains n strings or words made up of letters in A.  The words in W
have length <= n. Does there exist an integer k and a function f: Zk
-> Zn such that y = W[f(0)]*W[f(1)]*….*W[f(k-1)]?  * is the
concatenation operator.  In other words, is y a concatenation of words
in W?  Note: Zi is subset or equal of Z such that Zi = { 0, 1, … i –1
}.
Example: Suppose n = 7 and W = [a, ab, acb, bab, bb, bcb, cc],  If  y
= abbabab then y = ab*bab*ab so the answer is Yes.  If y = babbacc
then the answer is NO.  k = 3.   And f(0) = 1, f(1) = 3, f(2) = 1.

---

Request for Question Clarification by rbnn-ga on 18 Dec 2002 11:20 PST

There are a couple of issues here.

First, the phrase "fastest algorithm" is ambiguous. It is necessary to
specify a metric by which to measure "fastest" (e.g., worst case or
average case; over which distribution of inputs). Generally in
discussin algorithm theory  we would mean by fastest "smallest
worst-case asymptotic complexity" over some measure of size of the
inputs; however, if you are writing a text editor, for example, you
might have another metric in mind.

Second, the sentence "Given an integer n, an array W[0,…,n-1] and a
string y." is not grammatical. In particular, it is not clear to me
whether you are fixing n and W and have as input a string y to the
algorithm (in which case a trivial linear algorithm exists) or whether
the input to the algorithm is the triple {n,W,y} , in which case I
don't see any worst-case asymptotically better way than brute force
with quadratic complexity.

Third, to design and to explain an algorithm would require much more
time for me than the pricing guidelines at
http://answers.google.com/answers/pricing.html suggest for $10.