A15216 | $Double Strings$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

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

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

输入 #1

3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code

输出 #1

10100
011
10100101

C++ 编辑器

输入

输出