Elearning CodePath – CTP Online Judge

Double Palindrome

DPPALIN

🟢 Hard #String #Combinatorics

### 📌 Thông tin chung

---
### 📝 Định nghĩa

* **Palindrome:** Một chuỗi ký tự mà khi đọc từ trái qua phải hoặc từ phải qua trái đều như nhau (ví dụ: `aba`, `abba`).
* **Palindrome Kép (Double Palindrome):** Một chuỗi được ghép bởi hai chuỗi Palindrome có cùng độ dài.

Ví dụ:
* Chuỗi `aabb` là palindrome kép: ghép bởi `aa` (palindrome, dài 2) và `bb` (palindrome, dài 2).
* Chuỗi `aaaa` là palindrome kép: ghép bởi `aa` và `aa`.
* Chuỗi `abba` không là palindrome kép.
* Chuỗi `aaaabb` không là palindrome kép (dài 6, nếu chia đôi thành `aaa` và `abb` thì `abb` không phải palindrome).

Yêu cầu: Cho xâu $S$ có $N$ ký tự, tìm số cặp $(l, r)$ sao cho chuỗi con $S[l..r]$ là một chuỗi Palindrome Kép.

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

Dữ liệu vào từ file `DPPALIN.INP`:

* Dòng 1: Ghi số nguyên $N$ ($1 \le N \le 500000$).
* Dòng 2: Chứa chuỗi $S$ có $N$ ký tự. Các ký tự trong chuỗi là các chữ cái tiếng Anh in thường.

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

Ghi ra file `DPPALIN.OUT` một dòng duy nhất là số xâu con là chuỗi palindrome kép tìm được.

---
### ✨ Ví dụ

| Input | Output | Giải thích |
| :--- | :--- | :--- |
| `6` `abacac` | `6` | Các xâu con được đếm là: `ab`, `ba`, `ac`, `ca`, `ac` (5 chuỗi) và chuỗi `abacac` (chuỗi ban đầu, được coi là Palindrome Kép). $5+1=6$. |
| `5` `aaaaa` | `6` | Các chuỗi con Palindrome Kép: Độ dài 2 (4 chuỗi): `aa`, `aa`, `aa`, `aa`. Độ dài 4 (2 chuỗi): `aaaa`, `aaaa`. Tổng cộng: $4 + 2 = 6$. |

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $N \le 500$ | $19\%$ |
| 2 | $N \le 5000$ | $33\%$ |
| 3 | $N \le 500000$ | $48\%$ |

---

✅ Đã AC: 0 / 2 submissions