Gọi ~f[i]~ là tổng độ dài trong cách chia xâu và nén tối ưu của ~s[1...i]~ (tiền tố độ dài ~i~ của ~s~)

~\Rightarrow~ Ta có công thức truy hồi:

Trong đó, ~compress(s[j..i])~ là độ dài của xâu ~s[j..i]~ trong phương án nén tối ưu.

Từ công thức trên, ta có được thuật toán với độ phức tạp thời gian ~n^4~, trong đó để tính ~compress(s[j..i])~ ta mất ~n^2~

Ta xét một xâu ~s'~ có ~m~ kí tự, gọi ~p[1], p[2], ..., p[m]~ là dãy tiền tố của ~s'~ (~p~ có thể được tính theo thuật toán \href{https://vnoi.info/wiki/algo/string/kmp.md}{kmp}; có thể chứng minh:

• ~compress(s') = m - p[m]~ nếu ~m~ chia hết cho ~m-p[m]~
• ~compress(s') = m~ nếu nếu ~m~ không chia hết cho ~m-p[m]~

Từ đây ta suy ra thuật toán với độ phức tạp ~n^3~ bằng cách tính ~compress(s[j..i])~ sử dụng KMP

Nhận xét: Sử dụng thuật toán KMP, ta có thể tính được cùng lúc ~compress(s[i..i]), compress(s[i..i+1]),...,compress(s[i..n])~ bằng cách sử dụng dãy tiền tố của xâu ~s[i..n]~

~\Rightarrow~ Ta có thể thực hiện thuật toán ~n~ lần trên các xâu ~s[1..n], s[2..n],...,s[n..n]~ để tính trước số kí tự sau nén của mọi xáu con của ~s~.

Vậy, ta thu được thuật toán với độ phức tạp ~n^2~

Code mẫu: https://ideone.com/9NQTMQ