Xây dựng mảng ~f~ là mảng ~KMP~ cho xâu ~S~.

Gọi ~dp_i~ là số lần xuất hiện của xâu tiền tố độ dài ~i~ trong dãy ~S~, ta có công thức quy hoạch động như sau: ~dp_i = sum (dp_j) + 1~ với ~n \ge j > i~ và ~f_j = i~.

Để tính nhanh ~dp_i~, ta có thể sử dụng một mảng để lưu tổng tất cả các ~dp_j~ có chung ~f_j~.

Như vậy, ta đã có thể tính được số lần xuất hiện của mỗi tiền tố trong xâu. Bước tiếp theo ta cần tìm các xâu tiền tố đẹp.

Ta nhận thấy rằng, các tiền tố bằng với hậu tố của xâu ~S~ sẽ lần lượt có độ dài là ~n,f[n], f[f[n]], f[f[f[n]]], ...~ .Như vậy, có thể sử dụng KMP để tìm ra các xâu tiền tố thỏa mãn và in ra số lần xuất hiện trong xâu của chúng.