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}. Consider 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? A student claims: "At least the problem is in NP: I just have to show such a string u in order to prove the answer is yes." You point out that this explanation is insufficient: how do we know that the shortest such string is not exponential in the size of the input, in which case it would not be a polynomial-size certificate? Fix the argument, proving that 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.