[Solution] Double Strings CodeForces Solution

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 

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.

YES or YES? Codeforces Solution

ICPC Balloons Codeforces Solution

Cypher Codeforces Solution

Double Strings CodeForces Solution

Mirror Grid Codeforces Solution

Yet Another Problem About Pairs Satisfying an Inequality Codeforces Solution

Good Key, Bad Key Codeforces Solution

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.