27802번 - Pattern Matching 서브태스크스페셜 저지다국어채점 준비 중

Many terminals use asterisks (*) to signify "any string", including the empty string. For example, when listing files matching BASH*, a terminal may list BASH, BASHER and BASHFUL. For *FUL, it may list BEAUTIFUL, AWFUL and BASHFUL. When listing B*L, BASHFUL, BEAUTIFUL and BULL may be listed.

In this problem, formally, a pattern is a string consisting of only uppercase English letters and asterisks (*), and a name is a string consisting of only uppercase English letters. A pattern p matches a name m if there is a way of replacing every asterisk in p with a (possibly empty) string to obtain m. Notice that each asterisk may be replaced by a different string.

Given N patterns, can you find a single name of at most 10⁴ letters that matches all those patterns at once, or report that it cannot be done?

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with a single integer N: the number of patterns to simultaneously match. Then, N lines follow, each one containing a single string P_i representing the i-th pattern.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is any name containing at most 10⁴ letters such that each P_i matches y according to the definition above, or * (i.e., just an asterisk) if there is no such name.

• 1 ≤ T ≤ 100.
• 2 ≤ N ≤ 50.
• 2 ≤ length of P_i ≤ 100, for all i.
• Each character of P_i is either an uppercase English letter or an asterisk (*), for all i.
• At least one character of P_i is an uppercase English letter, for all i.

• Exactly one character of P_i is an asterisk (*), for all i.
• The leftmost character of P_i is the only asterisk (*), for all i.

• Exactly one character of P_i is an asterisk (*), for all i.

• At least one character of P_i is an asterisk (*), for all i.

In Sample Case #1, there are other possible answers, including COCOCONUTS and ILIKECOCONUTS. Neither COCONUTSAREGREAT nor COCOANUTS would be acceptable. Notice that the same pattern may appear more than once within a test case.

In Sample Case #2, there is no acceptable name, so the answer is *.

The following cases could not appear in Test Set 1, but could appear in Test Set 2 or Test Set 3:

  4
  H*O
  HELLO*
  *HELLO
  HE*

HELLO and HELLOGOODBYEHELLO are examples of acceptable answers. OTHELLO and HELLOO would not be acceptable.

  2
  CO*DE
  J*AM

There is no name that matches both patterns, so the answer would be *.

  2
  CODE*
  *JAM

CODEJAM is one example of an acceptable answer.

The following cases could not appear in Test Set 1 or Test Set 2, but could appear in Test Set 3:

  2
  A*C*E
  *B*D*

ABCDE and ABUNDANCE are among the possible acceptable answers, but BOLDFACE is not.

  2
  A*C*E
  *B*D

There is no name that matches both patterns, so the answer would be *.

  2
  **Q**
  *A*

QUAIL and AQ are among the possible acceptable answers here.