Double Strings solution codeforces

You are given n strings 1,2,,s1,s2,…,sn of length at most 88.

For each string si, determine if there exist two strings sj and sk such that =+si=sj+sk. That is, si is the concatenation of sj and sk. Note that j can be equal to k.

Double Strings solution codeforces

Recall that the concatenation of strings s and t is +=1212s+t=s1s2…spt1t2…tq, where p and q are the lengths of strings s and t respectively. For example, concatenation of “code” and “forces” is “codeforces“.

Input

The first line contains a single integer t (11041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n (11051≤n≤105) — the number of strings.

Then n lines follow, the i-th of which contains non-empty string si of length at most 88, 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 105105.

Double Strings solution codeforces

For each test case, output a binary string of length n. The i-th bit should be 1 if there exist two strings sj and sk where =+si=sj+sk, and 0 otherwise. Note that j can be equal to k.

Example
input 

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

Copy
10100
011
10100101

Double Strings solution codeforces

In the first test case, we have the following:

  • 1=2+2s1=s2+s2, since =+abab=ab+ab. Remember that j can be equal to k.
  • 2s2 is not the concatenation of any two strings in the list.
  • 3=2+5s3=s2+s5, since =+abc=ab+c.
  • 4s4 is not the concatenation of any two strings in the list.
  • 5s5 is not the concatenation of any two strings in the list.

Since only 1s1 and 3s3 satisfy the conditions, only the first and third bits in the answer should be 1, so the answer is 10100.

Leave a Comment

Your email address will not be published.