CF1476E Pattern Matching

You are given $ n $ patterns $ p_1, p_2, \dots, p_n $ and $ m $ strings $ s_1, s_2, \dots, s_m $ . Each pattern $ p_i $ consists of $ k $ characters that are either lowercase Latin letters or wildcard characters (denoted by underscores). All patterns are pairwise distinct. Each string $ s_j $ consists of $ k $ lowercase Latin letters. A string $ a $ matches a pattern $ b $ if for each $ i $ from $ 1 $ to $ k $ either $ b_i $ is a wildcard character or $ b_i=a_i $ . You are asked to rearrange the patterns in such a way that the first pattern the $ j $ -th string matches is $ p[mt_j] $ . You are allowed to leave the order of the patterns unchanged. Can you perform such a rearrangement? If you can, then print any valid order.

N/A

N/A

The order of patterns after the rearrangement in the first example is the following: - aaaa - \_\_b\_ - ab\_\_ - \_bcd - \_b\_d Thus, the first string matches patterns ab\_\_, \_bcd, \_b\_d in that order, the first of them is ab\_\_, that is indeed $ p[4] $ . The second string matches \_\_b\_ and ab\_\_, the first of them is \_\_b\_, that is $ p[2] $ . The last string matches \_bcd and \_b\_d, the first of them is \_bcd, that is $ p[5] $ . The answer to that test is not unique, other valid orders also exist. In the second example cba doesn't match \_\_c, thus, no valid order exists. In the third example the order (a\_, \_b) makes both strings match pattern $ 1 $ first and the order (\_b, a\_) makes both strings match pattern $ 2 $ first. Thus, there is no order that produces the result $ 1 $ and $ 2 $ .