Subtask 1

Duyệt toàn bộ xâu nghiệm có thể và kiểm tra.

Độ phức tạp là \(O(3^{L} \times L^{3})\) với \(L\) là độ dài xâu kết quả.

Subtask 2

Giả sử \(A, B\) là hai dẫn xuất của xâu kết quả. Ta sẽ duyệt để xây dựng từng ký tự của \(A, B\): Khi duyệt đến vị trí \(i\), ta cần kiểm soát phần cuối của \(A\) đang là một hậu tố trong tập \(S\).

Gọi \(x\) và \(y\) là hai tiền tố của tập \(S\) ứng với phần cuối của \(A, B\). Khi đó \((i, x, y)\) mô tả một trạng thái của quá trình duyệt. Gọi \(dp(i, x, y)\) là số ký tự ít nhất cần thêm vào \(A, B\) sao cho thu được hai dẫn xuất khác nhau của một xâu. Khi đó \(dp(i, x, y) = \min_{c:a \rightarrow z}(1 + dp(i + 1, x + c, y + c))\); nếu \(x\) là một xâu trong \(S\) thì cần cập nhật thêm \(dp(i + 1, '', y)\); nếu \(y\) là một xâu trong \(S\) thì cần cập nhật thêm \(dp(i + 1, x, '')\).

Ở đây \(x, y\) có thể được thay thế bởi \(1\) node trên cây tiền tố (trie tree) của tập \(S\).

Độ phức tạp: \(O(L\times sum^{2})\) với \(L\) là độ dài xâu kết quả và \(sum\) là tổng độ dài các xâu trong \(S\).

Subtask 3

Dựng đồ thị có tập đỉnh là tập các cặp \((x, y)\) với \(x, y\) là các tiền tố của tập \(S\). Từ đỉnh \((x, y)\) ta nối các cung có trọng số \(1\) đến \((x + c, y + c)\) với $c = a \ldots z$; các cung có trọng số \(0\) đến \(('', y)\) nếu \(x\) thuộc \(S\); \((x, '')\) nếu \(y\) thuộc \(S\). Bài toán đưa về tìm đường đi ngắn nhất trên đồ thị này và có thể giải bằng thuật toán BFS.

Độ phức tạp \(O(sum^{2})\) với \(sum\) là tổng độ dài các xâu trong \(S\).