[Solution] Double Strings solution codeforces

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.

Table of Contents

[Solution] Double Strings solution codeforces

Recall that the concatenation of strings 𝑠s and 𝑡t is 𝑠+𝑡=𝑠1𝑠2𝑠𝑝𝑡1𝑡2𝑡𝑞s+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 (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛1051≤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.

[Solution] 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

[Solution] 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.

For Solution

Click Here

Leave a Comment