Hint 1

Đề bài cho chúng ta 3 điều kiện về cấu trúc xâu:

• \(X\) có dạng *A*B* (Nghĩa là: chuỗi \(A\) nằm trọn vẹn ở phía trước chuỗi \(B\))
• \(Y\) có dạng *C*A* (Nghĩa là: chuỗi \(C\) nằm trọn vẹn ở phía trước chuỗi \(A\))
• \(Z\) có dạng *B*C* (Nghĩa là: chuỗi \(B\) nằm trọn vẹn ở phía trước chuỗi \(C\))

Dấu * đại diện cho các ký tự thừa có thể bỏ qua. Từ cấu trúc trên, ta có thể tưởng tượng việc cắt mỗi xâu ra làm 2 nửa bằng 3 "vách ngăn" ảo tại các vị trí \(i, j, k\):

1. Cắt xâu \(X\) tại vị trí \(i\) (\(0 \le i \le n\)):
2. Nửa trái \(X[1 \dots i]\) sẽ dùng để chứa \(A\).

3. Nửa phải \(X[i+1 \dots n]\) sẽ dùng để chứa \(B\).

4. Cắt xâu \(Y\) tại vị trí \(j\) (\(0 \le j \le n\)):

5. Nửa trái \(Y[1 \dots j]\) sẽ dùng để chứa \(C\).

6. Nửa phải \(Y[j+1 \dots n]\) sẽ dùng để chứa \(A\).

7. Cắt xâu \(Z\) tại vị trí \(k\) (\(0 \le k \le n\)):

8. Nửa trái \(Z[1 \dots k]\) sẽ dùng để chứa \(B\).
9. Nửa phải \(Z[k+1 \dots n]\) sẽ dùng để chứa \(C\).

Lắp ráp các nửa lại với nhau, ta rút ra bản chất cốt lõi của bài toán:

• Chuỗi \(A\) lớn nhất chính là Chuỗi con chung dài nhất của đoạn \(X[1 \dots i]\) và \(Y[j+1 \dots n]\).
• Chuỗi \(B\) lớn nhất chính là Chuỗi con chung dài nhất của đoạn \(X[i+1 \dots n]\) và \(Z[1 \dots k]\).
• Chuỗi \(C\) lớn nhất chính là Chuỗi con chung dài nhất của đoạn \(Y[1 \dots j]\) và \(Z[k+1 \dots n]\).

Nhiệm vụ bây giờ là tìm ra bộ ba \((i, j, k)\) sao cho tổng độ dài của \(A + B + C\) đạt giá trị Max.

Hint 2: Xây dựng mảng Quy hoạch động (DP) \(O(n^2)\)

Nếu với mỗi bộ ba \((i, j, k)\) ta lại viết một hàm chạy vòng lặp tìm chuỗi con chung, độ phức tạp sẽ vượt quá \(O(n^3)\) và chắc chắn bị Time Limit Exceeded (TLE). Giải pháp là ta sẽ tính trước (tiền xử lý) 3 mảng DP 2 chiều:

• F[i][j]: Chứa độ dài xâu \(A\) dài nhất.
• G[i][k]: Chứa độ dài xâu \(B\) dài nhất.
• H[j][k]: Chứa độ dài xâu \(C\) dài nhất.

Lấy mảng F[i][j] làm ví dụ, ta sẽ tính nó qua 3 bước như sau:

• Bước 2.1 - DP Cơ bản: Dùng mảng phụ dp[u][v] để tính độ dài chuỗi con chung kết thúc đúng tại ký tự thứ \(u\) của \(X\) và thứ \(v\) của \(Y\). Nếu \(X[u] == Y[v]\) thì dp[u][v] = dp[u-1][v-1] + 1.
  Khi đó, chuỗi chung này có độ dài là \(L\), nó sẽ chiếm một khoảng trong \(Y\) bắt đầu từ vị trí \((v - L + 1)\) đến \(n\). Ta cập nhật: F[u][v - L] = max(F[u][v - L], L).
• Bước 2.2 - Lan truyền độ dài: Nếu có một chuỗi con chung độ dài \(L\), hiển nhiên bên trong nó sẽ chứa các chuỗi con độ dài \(L-1\). Ta cần lan truyền giá trị này xuống bằng cách xóa bớt ký tự ở cuối \(X\) hoặc đầu \(Y\):
  F[i-1][j] = max(F[i-1][j], F[i][j] - 1)
F[i][j+1] = max(F[i][j+1], F[i][j] - 1)
• Bước 2.3 - Nới lỏng ranh giới (Mở rộng vùng tìm kiếm): Nếu ta có kết quả tốt nhất trong đoạn nhỏ, thì khi mở rộng đoạn đó ra, kết quả chỉ có thể lớn hơn hoặc bằng.
  F[i][j] = max(F[i][j], F[i-1][j], F[i][j+1])

(Các bạn áp dụng logic tương tự để xây dựng mảng G cho nửa sau X / nửa đầu Z; và mảng H cho nửa đầu Y / nửa sau Z nhé).

Hint 3: Tuyệt chiêu Cắt tỉa (Pruning) biến \(O(n^3)\) thành \(O(n^2)\)

Sau khi có 3 mảng F, G, H, công thức tìm đáp án là:
Ans = max( F[i][j] + G[i][k] + H[j][k] )

Duyệt 3 vòng lặp for i, for j, for k từ 1 đến \(n\) sẽ mất \(2000 \times 2000 \times 2000 = 8 \times 10^9\) phép toán. Trong môi trường thi đấu thực tế, C++ sẽ chạy mất khoảng 8 giây, còn Python thì sẽ sập nguồn (TLE).

Đây là lúc thuật toán Cắt tỉa nhánh (Pruning) thể hiện sức mạnh:

Hãy suy luận một chút trước khi bước vào vòng lặp \(k\) (vòng lặp trong cùng):

• Đứng tại vị trí \(i\) hiện tại, mảng \(G\) chứa \(B\) đạt giá trị lớn nhất khi nào? Đó là khi ta lấy toàn bộ xâu \(Z\) (tức là \(k = n\)). Vậy Max lý tưởng của nhánh này là G[i][n].
• Đứng tại vị trí \(j\) hiện tại, mảng \(H\) chứa \(C\) đạt giá trị lớn nhất khi nào? Đó là khi ta cũng lấy toàn bộ xâu \(Z\) (tức là \(k = 0\)). Vậy Max lý tưởng của nhánh này là H[j][0].

Từ đó ta suy ra: Tất cả các giá trị thực tế của vòng lặp \(k\) đều không bao giờ vượt qua được tổng F[i][j] + G[i][n] + H[j][0].

Mã giả áp dụng:

```text
Cho i chạy từ 0 đến n:
Cho j chạy từ 0 đến n:
Tổng_Lý_Tưởng_Nhất = F[i][j] + G[i][n] + H[j][0]

    NẾU (Tổng_Lý_Tưởng_Nhất <= Kỷ_Lục_Ans_Hiện_Tại):
        Bỏ qua luôn vòng lặp k! (continue)
        // Vì dù k có hoàn hảo đến mấy cũng không thể phá vỡ kỷ lục

    NẾU (Có tiềm năng phá kỷ lục):
        Cho k chạy từ 0 đến n:
            Ans = max(Ans, F[i][j] + G[i][k] + H[j][k])