Elearning CodePath – CTP Online Judge

Đếm Cặp Đăng nhập

GEN042

🟢 Easy #String #Hash

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho $N$ người dùng, mỗi người dùng $i$ có một mật khẩu riêng $P_i$.
Quy tắc đăng nhập bị lỗi: Đăng nhập thành công vào tài khoản có mật khẩu $P_j$ nếu chuỗi ký tự nhập vào chứa $P_j$ như là một xâu con liên tiếp (substring).

Yêu cầu: Mihael muốn tính số lượng cặp người dùng khác nhau $(i, j)$ sao cho:
> Người dùng $i$ sử dụng mật khẩu riêng của họ ($P_i$) để đăng nhập thành công vào tài khoản của người dùng $j$.

Điều này tương đương với việc mật khẩu $P_j$ là một xâu con của mật khẩu $P_i$.

$\text{Tìm số lượng cặp } (i, j) \text{ với } i \ne j \text{ sao cho } P_j \text{ là xâu con của } P_i$

---

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

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

* **Dòng 1:** Số nguyên dương $N$ – số lượng người dùng.
* **$N$ dòng sau:** Mỗi dòng chứa mật khẩu $P_i$ của người dùng thứ $i$.

**Giới hạn (Ràng buộc):**
* $1 \le N \le 20,000$
* Mật khẩu chỉ bao gồm các chữ cái Latin thường ('a' - 'z').
* Độ dài mỗi mật khẩu $1 \le \text{length}(P_i) \le 10$.

**Subtasks:**
* **Subtask 1 (40%):** $N \le 2,000$.
* **Subtask 2 (60%):** $N \le 20,000$.

---

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

Ghi ra file `PASS.OUT` một dòng duy nhất chứa số lượng cặp người dùng $(i, j)$ thỏa mãn yêu cầu.

---

### ✨ Ví dụ

| Input (`PASS.INP`) | Output (`PASS.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `3` `a` `b` `ab` | `2` | Mật khẩu: $P_1=\text{"a"}$, $P_2=\text{"b"}$, $P_3=\text{"ab"}$. Cặp $(i, j)$ thỏa mãn: $P_j$ là xâu con của $P_i$. 1. $P_1$ là xâu con của $P_3$: $P_3$ ("ab") đăng nhập $P_1$ ("a"). Cặp **(3, 1)**. 2. $P_2$ là xâu con của $P_3$: $P_3$ ("ab") đăng nhập $P_2$ ("b"). Cặp **(3, 2)**. $\implies$ Tổng cộng 2 cặp. |
| `4` `a` `ab` `a` `abc` | `7` | Mật khẩu: $P_1=\text{"a"}$, $P_2=\text{"ab"}$, $P_3=\text{"a"}$, $P_4=\text{"abc"}$. Cặp $(i, j)$ thỏa mãn: $P_j$ là xâu con của $P_i$. - $P_1$ là xâu con của $P_2$: (2, 1). - $P_3$ là xâu con của $P_2$: (2, 3). - $P_1$ là xâu con của $P_4$: (4, 1). - $P_2$ là xâu con của $P_4$: (4, 2). - $P_3$ là xâu con của $P_4$: (4, 3). - $P_1=P_3$: (1, 3) và (3, 1). $\implies$ Tổng cộng 7 cặp. |

---

✅ Đã AC: 0 / 0 submissions