Tóm tắt đề bài: Bạn được cho một mảng A có độ dài là N. Phần tử thứ A[i] là độ dài đoạn tiền tố chung dài nhất của 2 xâu thứ i và i + 1, tức là nếu A[1] = 2 thì xâu thứ 1 và thứ 2 có tiền tố chung dài nhất bằng 2, A[2] = 2 thì xâu thứ 2 và thứ 3 có tiền tố chung dài nhất bằng 2.
Vấn đề đặt ra là từ mảng độ dài các tiền tố, bạn phải tạo ra các xâu sao cho phù hợp với mảng độ dài tiền tố đó.
Hướng dẫn: Trước hết ta phải hiểu khái niệm đoạn tiền tố chung dài nhất, mình khuyến khích đọc lại đề vì đề miêu tả rất rõ rồi.
Giả sử ta có xâu s1 = "aaaaaa" và s2 là xâu copy lại s1, s2 = "aaaaaa". Khi đó nếu muốn xâu tiền tố dài nhất của 2 xâu này có độ dài i (1 <= i <= strlen(s1)), khi đó chỉ cần s1[i + 1] != s2[i + 1] thì thõa.
Vậy nếu i = strlen(s1) thì sao? Khi đó s1[i + 1] đâu có tồn tại đâu?
Chính vì vậy ta sẽ cố định độ dài các xâu sinh ra đều bằng strlen(s1) + 1. Một cách tổng quát hơn, ta cố định độ dài các xâu sinh ra là max(strlen(si)) + 1, (1 <= i <= N). Thực hiện biến đổi mỗi xâu như cách trên là giải quyết được vấn đề.
Ở code mẫu mình giải quyết cồng kềnh một chút là dùng alphabet 26 chữ cái, cái này có thể thay bằng xâu toàn 1 ký tự rồi đổi ký tự ở vị trí i thành một ký tự khác chẳng hạn.
No comments:
Post a Comment