Given a set of finite binary strings S = {s1, . . . , sk}, we say that a string u is a concatenation over S if it is equal to si1 si2 . . . sit for some indices i1, . . . , it {1, , k}.

A friend of yours is considering the following problem: Given two sets of finite binary strings, A = {a1, . . . , am} and B = {b1, , bn}, does there exist any string u so that u is both a concatenation over A and a concatenation over B?

Your friend announces, At least the problem is in NP, since I would just have to exhibit such a string u in order to prove the answer is yes. You point out (politely, of course) that this is a completely inadequate explanation; how do we know that the shortest such string u doesnt have length exponential in the size of the input, in which case it would not be a polynomial-size certiciate?

However, it turns out that this claim can be turned into a proof of membership in NP. Specifically, prove the following statement.

If there is a string u that is a concatenation over both A and B, then there is such a string whose length is bounded by a polynomial in the sum of the lengths of the strings in A B.