---
# System prepended metadata

title: Solution kén rể

---

# Solution kén rể
Gọi $lcs_{i, j}$ là độ dài hậu tố chung dài nhất của hai xâu $s[1..i]$ và $s[1..j]$. 
* $lcs_{i, j}$ = $0$ nếu $s_i$ $\neq$ $s_j$.
* $lcs_{i, j}$ = $1$ + $lcs_{i-1, j-1}$ nếu $s_i$ == $s_j$.

Ta có mảng $f[110][110]$ với $f_{i, j}$ = $1$ nếu trong xâu con liên tiếp từ $i$ đến $j$ của $s$ có chứa một xâu con giống xâu con xấu và = $0$ nếu ngược lại. Với mỗi xâu con xấu $l$, $r$ có độ dài $len$ = $r - l + 1$, ta đánh dấu mọi $f_{l', r'}$ = $1$ nếu $lcs_{r, r'}$ $\geq$ $len$ và $l'$ = $r' - len + 1$.
$f_{i, j}$ |= ($f_{i+1, j}$ || $f_{i, j-1}$)

Ta có mảng $dp[110][110][110]$ với $dp_{i, l, r}$ là số thao tác ít nhất Tèo cần sửa khi xét đến vị trí $i$ và phần hậu tố của xâu $t[1..i]$ hiện tại đang trùng với xâu con $l, r$ của xâu $s$ với $r - l + 1$ có độ dài max.

Ta for lần lượt kí tự c từ 'a' đến 'z' là kí tự ở vị trí $i+1$ của xâu $t$ để chuyển trạng thái. Nếu c = $t_{i+1}$ thì tèo không thay đổi kí tự $i+1$ và ngược lại. Gọi $l', r'$ là trạng thái mới của $l, r$ sau khi được thêm kí tự c vào sau. Nếu $f_{l', r'}$ = $1$ thì ta không được phép thay đổi kí tự $i+1$ của xâu $t$ thành c. 

Để tính $l', r'$ là trạng thái mới của $l, r$ sau khi thêm kí tự c vào sau, ta for r' từ $1$ đến $n$, nếu $s_{r'}$ = c, ta có $len$ = min($r-l+1, lcs_{r'-1, r}$). Ta chọn cặp $(l', r')$ có độ dài max.

ĐPT: O(n^3 * 26)