Double Strings (Codeforces 1703D)
Tags: Others, 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".

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

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

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

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

Sample Outputs:
10100
011
10100101

Solution (Python):
import bisect
import random
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def _miillerTest(d, n):
    a = 2 + random.randint(1, n - 4)
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    while d != n - 1:
        x = x * x % n
        d *= 2
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False

def _isprime(n):
    if n < 2 or n == 4:
        return False
    if n <= 3:
        return True
    d = n - 1
    while d % 2 == 0:
        d //= 2
    for i in range(5):
        if _miillerTest(d, n) == False:
            return False
    return True

def _gcd(a, b):
    return a if b == 0 else _gcd(b, a % b)

def _lcm(a, b):
    return a * b // _gcd(a, b)

def _mex(a):
    mex = 0
    a.sort()
    for x in a:
        if x <= mex:
            mex += 1
        else:
            break
    return mex

def _dist(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def _getprimes(n, m):
    primes = []
    if n <= 2:
        primes.append(2)
    if n % 2 == 0:
        n += 1
    for i in range(n, m + 1, 2):
        if _isprime(i):
            primes.append(i)
    return primes

def _primefactors(n):
    ret = []
    x = n
    i = 2
    if _isprime(n):
        ret.append(n)
        return ret
    while i * i <= x:
        while n % i == 0:
            ret.append(i)
            n //= i
            if _isprime(n):
                break
        i += 1
    if n > 1:
        ret.append(n)
    return ret

def _pollardrho(n):
    if n % 2 == 0:
        return 2
    if _isprime(n):
        return n
    while True:
        c = random.randint(2, n - 1)
        f = lambda x: x ** 2 + c
        x = y = 2
        d = 1
        while d == 1:
            x = f(x) % n
            y = f(f(y)) % n
            d = _gcd((x - y) % n, n)
        if d != n and _isprime(d):
            return d

def _sumdigit(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret

def _modinverse(n, m):
    return n % mod * (pow(m, mod - 2, mod) % mod) % mod

def p(n):
    return print(n, end=' ')

def lip(type=int):
    return list(map(type, input().split()))

def mip(type=int):
    return map(type, input().split())

def tip(type=int):
    return type(input())

def inp():
    return input()
yes = 'YES'
no = 'NO'

def solve(t):
    n = tip()
    d = {}
    a = []
    ans = ''
    for i in range(n):
        s = inp()
        a.append(s)
        d[s] = 1
    for i in range(n):
        q = a[i]
        ok = 0
        for j in range(1, len(a[i])):
            l = q[:j]
            r = q[j:]
            if l in d and r in d:
                ok = 1
                break
        if ok:
            ans += '1'
        else:
            ans += '0'
    print(ans)
t = 1
t = int(input())
for i in range(t):
    solve(i + 1)

Solution (Python):
I = input
for i in [0] * int(I()):
    n = int(I())
    a = [I() for i in range(n)]
    d = set(a)
    z = ['0'] * n
    for (i, s) in enumerate(a):
        for j in range(1, len(s)):
            if s[:j] in d and s[j:] in d:
                z[i] = '1'
    print(''.join(z))

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    s = [readline() for _ in range(n)]
    st = set(s)
    ans = ''
    for (i, x) in enumerate(s):
        ok = False
        for j in range(len(x) - 1):
            (a, b) = (x[:j + 1], x[j + 1:])
            if a in st and b in st:
                ok = True
                break
        ans += '1' if ok else '0'
    print(ans)

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()