Hướng dẫn giải của Mảnh Ghép Lời Tiên Tri

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Hướng tiếp cận

Đây là bài toán Shortest Superstring (Siêu xâu ngắn nhất) — một bài toán NP-hard kinh điển. Tuy nhiên, với $N \leq 18$ , ta có thể giải bằng quy hoạch động trên bitmask tương tự bài toán Người du lịch (TSP).

Nhận xét quan trọng

Loại bỏ xâu con: Nếu xâu $s_{j}$ là xâu con (substring) của xâu $s_{i}$ , thì $s_{j}$ không đóng góp gì vào siêu xâu — ta có thể bỏ nó. Bước này rất quan trọng vì nếu không loại bỏ, bitmask DP sẽ cho kết quả sai (DP tính overlap giữa suffix/prefix, không tính containment).
Overlap giữa hai xâu: Gọi $overlap (i, j)$ là độ dài dài nhất sao cho hậu tố (suffix) của $s_{i}$ trùng với tiền tố (prefix) của $s_{j}$ . Khi nối $s_{j}$ sau $s_{i}$ , ta chỉ cần thêm $| s_{j} | - overlap (i, j)$ ký tự.
Bài toán tương đương TSP: Tối thiểu hóa tổng độ dài siêu xâu tương đương với tối đa hóa tổng overlap. Mỗi xâu là một "thành phố", và ta cần tìm đường đi qua tất cả thành phố (permutation) sao cho tổng overlap lớn nhất.

Thuật toán

Bước 1: Tiền xử lý

Loại bỏ các xâu trùng lặp.
Loại bỏ các xâu là xâu con của xâu khác.
Gọi $m$ là số xâu còn lại sau khi loại bỏ.

Bước 2: Tính overlap

Với mỗi cặp $(i, j)$ trong $m$ xâu, tính $overlap (i, j)$ = độ dài dài nhất $k$ sao cho $s_{i}$ kết thúc bằng $k$ ký tự đầu của $s_{j}$ .
Có thể tính bằng brute force $O (m^{2} \cdot L)$ hoặc dùng KMP cho hiệu quả hơn.

Bước 3: Bitmask DP

$d p [mask] [i]$ = độ dài ngắn nhất của siêu xâu chứa đúng các xâu trong $mask$ , kết thúc bằng xâu $i$ .
Trạng thái gốc: $d p [1 ≪ i] [i] = | s_{i} |$ với mỗi $i$ .
Chuyển trạng thái: Với mỗi $mask$ , xâu cuối $last$ , và xâu tiếp theo $nxt \notin mask$ :

d p [mask \cup {n x t}] [n x t] = min (d p [mask] [l a s t] + | s_{n x t} | - overlap (l a s t, n x t))

Đáp án: ${min}_{i} d p [(1 ≪ m) - 1] [i]$

Độ phức tạp

Thời gian: $O (m^{2} \cdot L + 2^{m} \cdot m^{2})$ trong đó $L$ là tổng độ dài các xâu và $m \leq 18$ .
Bộ nhớ: $O (2^{m} \cdot m)$

Bình luận

Không có bình luận tại thời điểm này.