29779번 - Colliding Encoding 서브태스크다국어

Alan just had his first cryptography class in school today. He decided to apply what he learned and come up with his own cipher. He will map each English letter from A to Z to a decimal digit $0$ through $9$. He will then try to encode each word to a string consisting of decimal digits by replacing each letter in the word with its mapped digit.

In his excitement, Alan failed to notice that there are $26$ letters in the English alphabet and only $10$ decimal digits. As a result, there might be collisions, that is, pairs of different words whose encoding is the same.

Given a list of $\mathbf{N}$ words that Alan wants to encode and the mapping that he uses, can you find out if there would be any collisions between words on the list?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains $26$ decimal digits (integers between $0$ and $9$, inclusve) $\mathbf{D_A}, \mathbf{D_B}, \dots, \mathbf{D_Z}$, representing the mapping that Alan uses. A letter $\alpha$ is mapped to digit $\mathbf{D_\alpha}$.

The second line of each test case contains $\mathbf{N}$, the number of words Alan will encode.

The $i$-th of the last $\mathbf{N}$ lines contains a string $\mathbf{S_i}$, representing the $i$-th word Alan will encode.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is either YES, if there is at least one pair of different words from the list whose encoding coincides, and NO otherwise.

• $1 \le \mathbf{T} \le 100$.
• $0 \le \mathbf{D_\alpha} \le 9$, for all $\alpha$.
• $1 \le $ the length of $ \mathbf{S_i} \le 10$, for all $i$.
• Each character of $\mathbf{S_i}$ is an uppercase English letter A through Z, for all $i$.
• $\mathbf{S_i} \ne \mathbf{S_j}$, for all $i \ne j$.

• $1 \le \mathbf{N} \le 100$.

• $1 \le \mathbf{N} \le 6 \times 10^4$.

In Sample Case #1, the mapping for A is $0$, for B is $1$, for C is $2$, for D is $3$, and for E is $3$. With this mapping, ABC is encoded as $012$, BC is encoded as $12$, BCD as $123$, and CDE as $233$. Since all of these encodings are distinct, there are no collisions.

In Sample Case #2, the mapping for C is $2$, for D is $3$, for E is $3$, for F is $3$, and for G is $3$. With this mapping, CDE is encoded as $233$, DEF as $333$, and EFG as $333$. Since the encoding for DEF and EFG is the same, there is a collision.