Đây là một bài toán quy hoạch động kết hợp KMP điển hình.

Ta gọi ~dp_{i, j}~ là số lượng kí tự cần xóa nhỏ nhất khi xét ~i~ kí tự đầu của ~S~, ~j~ là độ dài hậu tố dài nhất của xâu đang xét trùng với tiền tố của xâu ~T~ (chính là mảng KMP).

Để chuyển trạng thái dễ dàng, ta xây dựng mảng ~next~ cùng mảng ~kmp~, ta có ~next_{i, c}~ là độ dài hậu tố dài nhất của xâu (~\pi_i + c~) trùng với tiền tố của xâu ~T~ (~\pi_i~ là tiền tố độ dài ~i~ của xâu ~T~).

Như vậy, khi xét ~dp_{i, j}~ ta có thể chuyển trạng thái như sau:

• Nếu giữ lại kí tự thứ i + 1, ta có ~dp_{i + 1, next_{j, S_{i + 1}}} = dp_{i, j}~.

• Nếu xóa kí tự thứ i + 1, ta có ~dp_{i + 1, j} = dp_{i, j} + 1~.

Kết quả sẽ là min(~dp_{|S|, i}~) với ~0 \leq i \leq |T|~. Code mẫu: https://ideone.com/RIt3QJ.