Bài toán: Cho n xâu có độ dài 1, 2, 3, …, n. Có bao nhiêu cách ghép để được độ dài xâu đúng bằng m? Biết s_i là tiền tố s_{i+1} và giả sử xâu chỉ có các kí tự Latinh thường.
Nếu như n xâu ban đầu mà s_i + s_j \neq s_j + s_i thì kết quả là 2^(n-1) rồi.
Nhưng ví dụ như s_1 = “a”, s_2 = “aa”, s_3 = “aaa”. thì chỉ tạo được 1 xâu duy nhất.
Bài này có thuật toán nào làm được không ạ?? Hash hay Z-function …
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?