Some queries on strings

Revision en3, by OneClickAC, 2019-09-02 19:51:07

Any leads on a better approach than $O(n^2)$ will be appreciated.

Question — You are given n strings and q queries. Each query is also in the form of a string (say $q_i$). You have to reply with true if this string can be formed by concatenating any of the n strings given earlier.

For example — Suppose $n = 3$ and the strings are $abc$ , $bc$ and $cd$.

So $abcabc$ is a valid string because you can use $abc$ twice. (There is no constraint on the number of times you can use any given string.)

Also, $bccdabc$ is a valid string as we can use the given strings in the order $2$, $3$ and $1$.

Sum of all the strings in query is $\leq 10000$

My friend final_tsu helped me in coming with a $O(n^2)$ approach using Trie and DP.

Thanks.

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 OneClickAC 2019-09-02 19:51:07 53
en2 OneClickAC 2019-09-02 14:36:18 28
en1 OneClickAC 2019-09-02 14:34:57 913 Initial revision (published)