1703D.md (2187B)
1 Source: https://codeforces.com/problemset/problem/1703/D 2 3 D. Double Strings 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given $n$ strings $s_1, s_2, \dots, s_n$ of length at most $\mathbf{8}$. 22 23 For each string $s_i$, determine if there exist two strings $s_j$ and $s_k$ such that $s_i = s_j + s_k$. That is, $s_i$ is the concatenation of $s_j$ and $s_k$. Note that $j$ can be equal to $k$. 24 25 Recall that the concatenation of strings $s$ and $t$ is $s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$, where $p$ and $q$ are the lengths of strings $s$ and $t$ respectively. For example, concatenation of "code" and "forces" is "codeforces". 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 30 31 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of strings. 32 33 Then $n$ lines follow, the $i$-th of which contains non-empty string $s_i$ of length at most $\mathbf{8}$, consisting of lowercase English letters. Among the given $n$ strings, there may be equal (duplicates). 34 35 The sum of $n$ over all test cases doesn't exceed $10^5$. 36 37 Output 38 39 For each test case, output a binary string of length $n$. The $i$-th bit should be $\texttt{1}$ if there exist two strings $s_j$ and $s_k$ where $s_i = s_j + s_k$, and $\texttt{0}$ otherwise. Note that $j$ can be equal to $k$. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 48 5 49 50 abab 51 52 ab 53 54 abc 55 56 abacb 57 58 c 59 60 3 61 62 x 63 64 xx 65 66 xxx 67 68 8 69 70 codeforc 71 72 es 73 74 codes 75 76 cod 77 78 forc 79 80 forces 81 82 e 83 84 code 85 ``` 86 87 Output 88 89 ``` 90 10100 91 011 92 10100101 93 ``` 94 95 Note 96 97 In the first test case, we have the following: 98 99 * $s_1 = s_2 + s_2$, since $\texttt{abab} = \texttt{ab} + \texttt{ab}$. Remember that $j$ can be equal to $k$. 100 * $s_2$ is not the concatenation of any two strings in the list. 101 * $s_3 = s_2 + s_5$, since $\texttt{abc} = \texttt{ab} + \texttt{c}$. 102 * $s_4$ is not the concatenation of any two strings in the list. 103 * $s_5$ is not the concatenation of any two strings in the list. 104 105 Since only $s_1$ and $s_3$ satisfy the conditions, only the first and third bits in the answer should be $\texttt{1}$, so the answer is $\texttt{10100}$.