Wildcard File Matching

This problem requires you to simulate the command line interface file matching using wildcards. The two wildcards available are:

• *: matches zero or more arbitrary characters.
• ?: matches exactly one arbitrary character.

Given a list of file names and a wildcard pattern, your task is to output all file names that match the given pattern in the same order as input.

The matching follows the rules below:

• Let \( s \) be a file name and \( p \) be the pattern. Then, the matching condition can be formulated using the recurrence:</p>

  \[ \text{dp}(i, j) = \begin{cases} \text{true} & \text{if } i = 0 \text{ and } j = 0,\\ \text{dp}(0, j) = \text{dp}(0, j-1), & \text{if } p_{j-1}=* \\ \text{dp}(i, j) =\text{dp}(i-1, j-1), & \text{if } p_{j-1} = ? \text{ or } s_{i-1}=p_{j-1},\\ \text{dp}(i, j) =\text{dp}(i, j-1) \text{ or } \text{dp}(i-1, j), & \text{if } p_{j-1}=* \end{cases} \]

  where \( 0 \leq i\leq |s| \) and \( 0 \leq j \leq |p| \).

  inputFormat

  The input consists of several lines:

  1. The first line contains a positive integer n indicating the number of file names.
  2. The next n lines each contain a file name (a non-empty string without spaces).
  3. The last line contains the wildcard pattern.

  outputFormat

  Output all file names that match the given pattern, each on a separate line. If no file name matches, output nothing.

  sample

  4
  file.txt
  file1.txt
  file2.doc
  document.txt
  file*.txt

  file.txt
  file1.txt