Vĩnh Phúc - HSG - THCS - 2025

Bài 3 - Xâu rút gọn.

Xét xâu \(T\), gọi \(nxt[i][j]\) là vị trí của ký tự \(j\) gần nhất, tính từ ký tự thứ \(i\) đến ký tự thứ \(n\), \(-1\) nếu không có.

Dễ dàng tính được bằng công thức truy hồi sau:

• \(nxt[n + 1][j] = -1\).
• \(nxt[i][j] = i\) nếu \(s_i = j\).
• \(nxt[i][j] = nxt[i + 1][j]\) nếu \(s_i \neq j\).

Ban đầu, đặt \(pos = 0\), \(res = 1\) với ý nghĩa: xâu hiện tại đã dùng hết \(0\) ký tự, và kết quả đang là \(1\).

Lần lượt duyệt từng ký tự \(c\) của xâu \(S\). Có ba trường hợp:

• Nếu \(nxt[pos + 1][c] \neq -1\), nghĩa là xâu \(T\) hiện tại vẫn có thể có thêm một ký tự của xâu \(S\), ta sẽ đặt \(pos = nxt[pos + 1][c]\).
• Nếu \(nxt[1][c] \neq -1\), nghĩa là nếu tạo xâu \(T\) mới, ta có thể có thêm một ký tự của xâu \(S\), ta sẽ cộng \(res\) lên \(1\), và đặt \(pos = nxt[1][c]\).
• Cuối cùng, nếu tạo thêm một xâu \(T\) nữa, vẫn không có ký tự \(c\), kết quả là \(-1\) và ta kết thúc chương trình.

Dễ dàng nhận ra, khi và chỉ khi tồn tại một ký tự \(c\) có trong \(S\) mà không có trong \(T\), kết quả sẽ là \(-1\).

Độ phức tạp: \(O\) \((|T| \times 26 + |S|)\).

Bài 4 - Dãy đẹp.

Gọi \(dp[i][mx][mul]\) là kết quả khi xét đến phần tử thứ \(i\), \(mx\) là trạng thái của đoạn con có tổng lớn nhất (\(0\) nếu chưa đến, \(1\) nếu đang xây dựng (hay các phần tử đang được thêm vào), \(2\) là đã xây dựng xong dãy), \(mul\) là trạng thái của dãy ta nhân với \(x\) (tương tự như vậy, \(0\) nếu chưa đến, \(1\) nếu đang xây dựng, \(2\) là đã xây dựng xong).

Rõ ràng, \(dp[0][0][0] = 0\), còn lại tất cả đều \(= -inf\).

Có hai cách chuyển trạng thái. Tại mọi thời điểm, ta có thể chuyển trạng thái \(mx\) và \(mul\) như sau: từ \(0\) (chưa bắt đầu) thành \(1\) (đang xây dựng), hay từ \(1\) (đang xây dựng) thành \(2\) (đã xây dựng xong). Lưu ý, chúng ta cũng đã xét trường hợp không nhân đoạn con nào.

Kết quả sẽ nằm ở \(dp[n][2][2]\).

Độ phức tạp: \(O\) \((n)\).