CF1703D.Double Strings

You are given $n$ strings $s_1, s_2, \dots, s_n$ of length at most $\mathbf{8}$.

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$.

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".

给你 $n$ 个长度不超过 $\mathbf{8}$ 的字符串 $s_1, s_2, \dots, s_n$。

对每个字符串 $s_i$，判断是否存在两个字符串 $s_j$ 和 $s_k$，使得 $s_i = s_j + s_k$。即 $s_i$ 是 $s_j$ 与 $s_k$ 的拼接。注意：$j$ 可以等于 $k$。

回顾一下，字符串 $s$ 与 $t$ 的拼接定义为 $s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$，其中 $p$ 和 $q$ 分别是字符串 $s$ 和 $t$ 的长度。例如，“code” 与 “forces” 的拼接结果是 “codeforces”。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of strings.

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).

The sum of $n$ over all test cases doesn't exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 字符串的数量。

接下来是 $n$ 行，其中第 $i$ 行包含一个非空字符串 $s_i$，其长度至多为 $\mathbf{8}$，且仅由小写英文字母组成。在给定的 $n$ 个字符串中，可能存在相等的字符串（即重复项）。

所有测试用例的 $n$ 值之和不超过 $10^5$。

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$.

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串。其中第 $i$ 位应为 $\texttt{1}$，当且仅当存在两个字符串 $s_j$ 和 $s_k$，使得 $s_i = s_j + s_k$；否则为 $\texttt{0}$。注意，$j$ 可以等于 $k$。

In the first test case, we have the following:

• $s_1 = s_2 + s_2$, since $\texttt{abab} = \texttt{ab} + \texttt{ab}$. Remember that $j$ can be equal to $k$.
• $s_2$ is not the concatenation of any two strings in the list.
• $s_3 = s_2 + s_5$, since $\texttt{abc} = \texttt{ab} + \texttt{c}$.
• $s_4$ is not the concatenation of any two strings in the list.
• $s_5$ is not the concatenation of any two strings in the list.

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}$.

在第一个测试用例中，我们有如下情况：

• $s_1 = s_2 + s_2$，因为 $\texttt{abab} = \texttt{ab} + \texttt{ab}$。注意 $j$ 可以等于 $k$。
• $s_2$ 不能表示为列表中任意两个字符串的拼接。
• $s_3 = s_2 + s_5$，因为 $\texttt{abc} = \texttt{ab} + \texttt{c}$。
• $s_4$ 不能表示为列表中任意两个字符串的拼接。
• $s_5$ 不能表示为列表中任意两个字符串的拼接。

由于只有 $s_1$ 和 $s_3$ 满足条件，因此答案中仅第一位和第三位应为 $\texttt{1}$，故答案为 $\texttt{10100}$。