Mảnh Ghép Lời Tiên Tri

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\le 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

1. 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).

2. Overlap giữa hai xâu: Gọi $\text{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|-\text{overlap}(i,j)$ ký tự.

3. 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 $\text{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·L)$ hoặc dùng KMP cho hiệu quả hơn.

Bước 3: Bitmask DP

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

Độ phức tạp

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