Với bài tập này ta sẽ sử dụng kiến thức liên quan đến KMP

Định nghĩa ~{\pi[i]}~ là độ dài tiền tố lớn nhất của xâu ~T[0..i]~ mà cũng là hậu tố của xâu đó.

Trước tiên, ta nhận xét để tạo ra xâu có độ dài n, ta cần nối xâu ~S~ với với một xâu ~K~ có độ dài là n - m. Xây dựng một xâu ~T~ có độ dài là ~{min(m, n - m)}~ với ~T~ là một tiền tố của xâu ~S~.

Từ đó bài toán của ta trở thành số cách khác nhau để tạo xâu ~K~ từ ~prefix~ của xâu ~T~. Gọi ~{dp[i]}~ là số các xâu khác nhau độ dài ~{i}~ có thể tạo. Công thức tổng quát sẽ là ~{dp[i] = \sum dp[i - j]}~ với ~j~ thỏa mãn ~{\pi[j - 1] = 0}~.

Chứng minh: Nhận thấy ta chỉ thêm vào các ~prefix~ của ~T~ có ~{\pi[i]}~ ~=0~, do nếu không làm như vậy khi quy hoạch động ta sẽ bị trùng xâu. Giả sử ta chọn tiền tố ~{T[0...i]}~ có ~{\pi[i] \neq 0}~. Do ~{T[0...i]}~ = ~{T[0...i - \pi[i]]}~ + ~{T[0...\pi[i] - 1]}~, ta có thể chọn 2 tiền tố độ dài ~i - \pi[i] + 1~ và ~\pi[i]~ thay vì tiền tố độ dài ~i + 1~.