Elearning CodePath – CTP Online Judge

Truy vấn Mẫu

OOP

🟢 Easy #Tree

### 📌 Thông tin chung

| Mục | Chi tiết |
| :--- | :--- |
| **Tên File Input** | `OOP.INP` |
| **Tên File Output** | `OOP.OUT` |
| **Độ phức tạp mong muốn** | $O(\sum \text{Length} \cdot \alpha)$ (Với $\alpha$ là hệ số cho việc duyệt Trie) |

---

### 📝 Bài toán

Cho một tập hợp $N$ từ (Word set). Mỗi từ chỉ chứa các chữ cái Latin thường.
Cho $Q$ truy vấn, mỗi truy vấn là một **Mẫu** (Pattern). Mẫu bao gồm:
1.  **Một** ký tự đại diện '\*' duy nhất (Wildcard).
2.  Các chữ cái Latin thường.

**Định nghĩa "Bao gồm" (Match):** Một Mẫu $P$ được cho là **bao gồm** một từ $W$ nếu tồn tại một mảng các chữ cái (có thể rỗng) mà khi thay thế cho ký tự '\*' trong $P$, thì Mẫu mới và từ $W$ trở nên giống hệt nhau.

Yêu cầu: Với mỗi Mẫu truy vấn, hãy tính số lượng từ trong tập hợp ban đầu mà Mẫu đó **bao gồm** (tức là số từ khớp với Mẫu).

---

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `OOP.INP` gồm:

* **Dòng 1:** Hai số nguyên dương $N$ và $Q$ – số lượng từ và số lượng truy vấn.
* **$N$ dòng tiếp theo:** Mỗi dòng chứa một từ của tập hợp.
* **$Q$ dòng cuối cùng:** Mỗi dòng chứa một Mẫu truy vấn.

**Giới hạn (Ràng buộc):**
* $1 \le N, Q \le 100,000$
* Tổng số ký tự trong tất cả các từ và tất cả các mẫu $\le 3,000,000$.
* Các từ và mẫu chỉ chứa các chữ cái Latin thường ('a' - 'z') và Mẫu chứa **đúng một** ký tự '\*'.

**Subtasks:**
* **40% điểm:** $1 \le N, Q \le 1000$.

---

### 📤 Định dạng Đầu ra

Ghi ra file `OOP.OUT` gồm $Q$ dòng. Dòng thứ $k$ chứa một số nguyên duy nhất là số lượng từ mà Mẫu thứ $k$ bao gồm.

---

### ✨ Ví dụ

| Input (`OOP.INP`) | Output (`OOP.OUT`) |
| :--- | :--- |
| `3 3` `aaa` `abc` `aba` `a*a` `aaa*` `*aaa` | `2` `1` `1` |

---

### 🧪 Giải thích Ví dụ

Tập từ: $W = \{\text{"aaa"}, \text{"abc"}, \text{"aba"}\}$.

1.  **Mẫu: `a*a`**
    * Khớp với "aaa" (thay * bằng "a").
    * Không khớp với "abc".
    * Khớp với "aba" (thay * bằng "b").
    * $\implies$ **2** từ.

2.  **Mẫu: `aaa*`**
    * Khớp với "aaa" (thay * bằng "").
    * Không khớp với "abc", "aba".
    * $\implies$ **1** từ.

3.  **Mẫu: `*aaa`**
    * Khớp với "aaa" (thay * bằng "").
    * Không khớp với "abc", "aba".
    * $\implies$ **1** từ.

✅ Đã AC: 0 / 0 submissions