I. Những bài toán cơ sở

Trong Lập trình thi đấu, xâu palindrome (xâu đối xứng) là một loại xâu kí tự đặc biệt. Đó là những xâu mà viết xuôi hay viết ngược đều giống nhau, chẳng hạn như ABBA hay TOEICCIEOT,...Nhờ tính chất đặc biệt này, người ta phát triển ra rất nhiều bài toán liên quan tới xâu palindrome, không chỉ ở trong xâu kí tự mà còn có thể phát triển sang các bài tập trên dãy số, nhưng chủ yếu là dạng bài tập Quy hoạch động.

Trong chuyên đề này, tôi sẽ giới thiệu tới các bạn một số bài tập như vậy. Nhưng trước hết ta hãy cùng đến với những bài toán cơ sở trước đã.

1. Kiểm tra xâu palindrome

Đề bài

Cho một xâu kí tự $s$ độ dài $n$. Kiểm tra xem xâu đó có phải xâu palindrome không?

Input:

• Dòng đầu tiên chứa số nguyên dương $T$ - số lượng test cases.
• Chứa duy nhất xâu kí tự $s$ độ dài $n$.

Ràng buộc:

• $1 \le T \le 100$.
• $1 \le n \le 10^6$.

Output:

• In ra Yes nếu xâu $s$ đối xứng, ngược lại in ra No. Kết quả của mỗi test case in ra trên một dòng.

Sample Input:

2
ABA
TOEIC

Sample Output:

Yes
No

Ý tưởng

Đây là một bài tập đơn giản mà bạn nào cũng phải làm qua khi mới bắt đầu học về xâu kí tự trong lập trình. Mặc dù vậy, tôi vẫn nói tới bài toán này vì ở những bài tập tiếp theo, chúng ta sẽ dùng nhiều tới việc kiểm tra tính đối xứng của một xâu.

Giả sử ta đánh số thứ tự của các kí tự trong xâu từ $0$ và kết thúc tại $n - 1$. Một xâu là đối xứng khi và chỉ khi nó thỏa mãn điều kiện:

$$s_i = s_{n - i - i}; \forall i: 0 \le i \le \left\lfloor{\frac{n - 1}{2}} \right\rfloor$$

Vậy ta kiểm tra bằng một vòng lặp, độ phức tạp $O(n)$.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h> using namespace std; bool is_palin(string &s)
{ int n = s.size(); for (int i = 0; i <= (n - 1) / 2; ++i) if (s[i] != s[n - i - i]) return false; return true;
} main()
{ int t; cin >> t; while (t--) { string s; cin >> s; if (is_palin(s)) cout << "Yes" << endl; else cout << "No" << endl; }
}

Ngôn ngữ Python:

def is_palin(s): n = len(s) for i in range((n - 1) / 2 + 1): if s[i] != s[n - i - 1]: return False return True if __name__ == '__main__': t = int(input()) for _ in range(t): s = input() if is_palin(s): print(Yes) else: print(No)

2. Xâu con palindrome dài nhất

Đề bài

Cho một xâu $s$ độ dài $n$. Hãy xác định độ dài xâu con đối xứng dài nhất trong $s?$

Input:

• Một dòng duy nhất chứa xâu kí tự $s$ độ dài $n$.

Ràng buộc:

• $1 \le n \le 1000$.

Output:

• In ra độ dài của xâu con đối xứng dài nhất tìm được trong $s$.

Sample Input:

abcddcbfgh

Sample Output:

6

Ý tưởng

Cách làm duyệt mọi xâu con trong xâu ban đầu rồi kiểm tra tính đối xứng của từng xâu, chắc chắn không thể thỏa mãn yếu tố thời gian thực thi nên ta sẽ không bàn tới nữa.

Bài toán này có nhiều cách tiếp cận với những độ phức tạp khác nhau, nhưng ở đây tôi sẽ hướng dẫn các bạn hướng tiếp cận đơn giản nhất với độ phức tạp là $O(n^2)$ là quy hoạch động.

Gọi $\text{palin}[i][j]$ là mảng đánh dấu xâu con $s_{i, j}$ có phải xâu đối xứng hay không: $\text{palin}[i][j] = 1$ nếu xâu con $s_{i, j}$ đối xứng, ngược lại thì $\text{palin}[i][j] = 0$.

Xét cặp kí tự $s_i, s_j,$ ta xây dựng công thức truy hồi để tính $\text{palin}[i][j]$ như sau:

• Nếu $s_i = s_j,$ thì xâu con $s_{i...j}$ có đối xứng hay không sẽ phụ thuộc vào xâu con $s_{i + 1, j - 1}$. Thiết lập công thức:

  $$\text{palin}[i][j] = \text{palin}[i + 1][j - 1]$$

• Nếu $s_i \ne s_j,$ hiển nhiên xâu con $s_{i...j}$ không đối xứng, ta có công thức:

  $$\text{palin}[i][j] = 0$$

Về cơ sở quy hoạch động, dễ dàng nhận ra:

• Xâu con có $1$ kí tự luôn luôn là đối xứng: $\text{palin}[i][j] = 1$.
• Xâu con có $2$ kí tự đối xứng hay không tùy vào hai kí tự đó: $\text{palin}[i][i + 1] = 1$ nếu $s_i = s_{i + 1}$.

Cuối cùng kết quả sẽ là $\text{max}(j - i + 1)$ với các căp $(i, j)$ thỏa mãn $\text{palin}[i][j] = 1$.

Độ phức tạp của cách này là $O(n^2)$.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h> using namespace std; main()
{ string s; cin >> s; s = ' ' + s; int n = s.size() - 1; vector < vector < int > > palin(n + 1, vector < int >(n + 1, 0)); // Cơ sở quy hoạch động. for (int i = 1; i <= n; ++i) { palin[i][i] = 1; if (i < n) palin[i][i + 1] = (a[i] == a[i + 1]); } // Tính bảng phương án. for (int j = n; j >= 3; --j) for (int i = 1; i <= j - 2; ++i) palin[i][j] = (palin[i + 1][j - 1] & (s[i] == s[j])); // Tìm kết quả cuối cùng. int res = 0; for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) if (palin[i][j]) res = max(res, j - i + 1); cout << res;
}

Ngôn ngữ Python:

if __name__ == '__main__': s = ' ' + input() n = len(s) - 1 # Cơ sở quy hoạch động. palin = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): palin[i][i] = 1 if i < n: palin[i][i + 1] = 1 if s[i] = s[i + 1] else 0 # Tính bảng phương án. for j in range(n, 2, -1): for i in range(1, j - 1): palin[i][j] = (palin[i + 1][j - 1] and s[i] == s[j]) # Tìm kết quả cuối cùng. res = 0 for i in range(1, n + 1): for j in range(i, n + 1): if palin[i][j]: res = max(res, j - i + 1) print(res)

II. Một số bài toán khác liên quan

1. Chia xâu thành các Palindromes

Đề bài

Cho một xâu $s$ độ dài $n$. Hãy tìm cách chia nó thành một số ít nhất các xâu con liên tiếp, sao cho mỗi xâu con đều là một palindrome?

Input:

• Một dòng duy nhất chứa xâu kí tự $s$ độ dài $n$.

Ràng buộc:

• $1 \le n \le 1000$.

Output:

• Một số nguyên duy nhất là số lượng đoạn tối thiểu chia được.

Sample Input:

abacc

Sample Output:

2

Giải thích:

Chia xâu ban đầu thành $2$ xâu con đối xứng là aba và cc.

Ý tưởng

Coi rằng xâu $s$ ban đầu được đánh số kí tự từ vị trí $1$.

Vẫn sử dụng quy hoạch động, ta sẽ gọi $dp[i]$ là số lượng xâu con đối xứng tối thiểu chia được từ xâu $s_{1...i}$. Công thức được thiết lập khá đơn giản: Nếu như đoạn $s_{j + 1...i}$ là một xâu đối xứng thì $dp[i]$ có thể gán bằng $dp[j] + 1$. Mà ta mong muốn kết quả nhỏ nhất, vì thế:

$$dp[i] = \text{min}\big(dp[j] + 1\big)$$

với xâu con $s_{j + 1...i}$ là đối xứng

Đến đây, công việc còn lại là kiểm tra một xâu con $s_{j...i}$ có phải đối xứng hay không. Nếu như sử dụng lại vòng lặp, thì độ phức tạp thuật toán sẽ là $O(n^3),$ không thể đáp ứng giới hạn $n \le 1000$. Thay vào đó, ta sẽ khởi tạo trước một mảng $\text{palin}[i][j]$ giống như bài toán trước để xác định đoạn $[i...j]$ có phải là một xâu đối xứng hay không bằng hai vòng lặp. Sau đó, giải thuật sẽ trở thành:

$$dp[i] = \text{min}\big(dp[j] + 1\big); \text{nếu } f[j + 1][i] = 1$$

Cơ sở quy hoạch động khởi tạo $dp[i] = \infty; \forall i: 1 \le i \le n$. Riêng $dp[1] = 1$.

Độ phức tạp giải thuật lúc này giảm xuống $O(n^2)$.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h> using namespace std; vector < vector < int > > data_preparation(string &s, int n)
{ vector < vector < int > > palin(n + 1, vector < int >(n + 1, 0)); for (int i = 1; i <= n; ++i) { palin[i][i] = 1; if (i < n) palin[i][i + 1] = (s[i] == s[i + 1]); } for (int j = n; j >= 3; --j) for (int i = 1; i <= j - 2; ++i) palin[i][j] = (palin[i + 1][j - 1] & (s[i] == s[j])); return palin;
} void solution(int n, vector < vector < int > > &palin)
{ vector < int > dp(n + 1, 1001); dp[1] = 1; for (int i = 2; i <= n; ++i) for (int j = i - 1; j >= 0; --j) if (palin[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1); cout << dp[n];
} main()
{ string s; cin >> s; s = ' ' + s; int n = s.size() - 1; vector < vector < int > > palin = data_preparation(s, n); solution(n, palin);
}

Ngôn ngữ Python:

def data_preparation(s, n): palin = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): palin[i][i] = 1 if i < n: palin[i][i + 1] = 1 if s[i] = s[i + 1] else 0 for j in range(n, 2, -1): for i in range(1, j - 1): palin[i][j] = (palin[i + 1][j - 1] and s[i] == s[j]) return palin def solution(s, n, palin): dp = [1001] * (n + 1) dp[1] = 1 for i in range(2, n + 1): for j in range(0, i): if palin[j + 1][i]: dp[i] = min(dp[i], dp[j] + 1) print(dp[n]) if __name__ == '__main__': s = ' ' + input() n = len(s) - 1 palin = data_preparation(s, n) solution(n, palin)

2. Đếm số xâu con là Palindrome

Đề bài

Cho một xâu kí tự $s$ độ dài $n$. Ở đây, ta định nghĩa "xâu con" của $s$ là một hoặc một số kí tự không cần liên tiếp nhau của $s,$ giữ nguyên thứ tự của chúng trong xâu ban đầu.

Hãy đếm số lượng "xâu con" là đối xứng của $s?$

Input:

• Một dòng duy nhất chứa xâu kí tự $s$ độ dài $n$.

Ràng buộc:

• $1 \le n \le 1000$.

Output:

• In ra một số nguyên là số lượng xâu con đối xứng của $s$. Do kết quả có thể rất lớn, chỉ cần in ra phần dư của kết quả sau khi chia cho $10^9 + 7$.

Sample Input:

IOICAMP

Sample Output:

9

Giải thích:

Các xâu con đối xứng là: I, O, I, C, A, M, P, II, IOI.

Ý tưởng

Ý tưởng của bài tập này là sử dụng quy hoạch động. Ta nhận ra bài toán có bản chất đệ quy, bởi nếu coi $dp[i][j]$ là số xâu con đối xứng trong đoạn vị trí $[i, j]$ của $s,$ thì ta xây dựng được công thức truy hồi như sau:

• Nếu $s_i \ne s_j,$ thì số lượng xâu con đối xứng của đoạn $[i, j]$ chỉ phụ thuộc vào số lượng xâu con đối xứng của đoạn $[i + 1, j]$ và $[i, j - 1]$. Ngoài ra, ta lại phải trừ bớt đi số lượng xâu con bị trùng lặp hai lần tính trong đoạn $[i + 1, j - 1]$. Tức là:

  $$dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]$$

• Nếu $s_i = s_j,$ thì số lượng xâu con đối xứng của của đoạn $[i, j]$ sẽ có thêm một xâu là $s_is_j,$ đồng thời cũng cộng với số lượng xâu con đối xứng ở giữa gộp từ hai đoạn $[i + 1, j], [i, j - 1]$ và trừ bớt đi số lượng xâu con bị trùng lặp hai lần tính trong đoạn $[i + 1, j - 1]$. Tuy nhiên, cần lưu ý rằng, bây giờ mỗi xâu con đối xứng trong đoạn $[i + 1, j - 1]$ lại có thể tạo thành thêm một xâu con đối xứng nữa bằng cách ghép $s_i$ và $s_j$ vào hai đầu xâu đó. Vì thế, ta có công thức:

  $$dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1$$

  $$= dp[i + 1][j] + dp[i][j - 1] + 1$$

Cơ sở quy hoạch động của bài toán là $dp[i][i] = 1$ - mọi đoạn độ dài $1$ đều chỉ có $1$ xâu con đối xứng. Kết quả cuối cùng dĩ nhiên là $dp[1][n]$.

Bằng hai vòng lặp, ta có thể tính được bảng phương án trong $O(n^2)$. Lưu ý cần kết hợp với đồng dư để đưa ra được kết quả đề bài yêu cầu.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>
#define int long long using namespace std; const int mod = 1e9 + 7; void solution(string &s, int n)
{ vector < vector < int > > dp(n + 1, vector < int >(n + 1)); for (int i = 1; i <= n; ++i) dp[i][i] = 1; for (int l = 2; l <= n; ++l) for (int i = 1; i <= n - l + 1; ++i) { int j = i + l - 1; dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod; if (s[i] == s[j]) (dp[i][j] += 1) %= mod; else dp[i][j] = (dp[i][j] - dp[i + 1][j - 1] + mod) % mod; } cout << dp[1][n];
} main()
{ string s; cin >> s; s = ' ' + s; int n = s.size() - 1; solution(s, n);
}

Ngôn ngữ Python:

def solution(s, n): mod = 10**9 + 7 dp = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): dp[i][i] = 1 for l in range(2, n + 1): for i in range(1, n - l + 2): j = i + l - 1 dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod if s[i] == s[j]: (dp[i][j] += 1) %= mod else: (dp[i][j] -= dp[i + 1][j - 1]) %= mod print(dp[1][n]) if __name__ == '__main__': s = ' ' + input() n = len(s) - 1 solution(s, n)

3. Xóa xâu con

Đề bài

Cho xâu kí tự $s$ chỉ gồm các chữ cái latin in thường. Ở mỗi bước, bạn được phép chọn ra một xâu con liên tiếp của $s$ và xóa nó đi, với điều kiện xâu con đó phải là xâu đối xứng.

Hãy đếm số bước ít nhất để xóa toàn bộ xâu $s?$

Input:

• Dòng đầu tiên chứa số nguyên dương T – số lượng test cases.
• $T$ dòng tiếp theo, mỗi dòng chứa một xâu kí tự $s$.

Ràng buộc:

• $1 \le T \le 5$.
• $1 \le |s| \le 300;$ với $|s|$ là độ dài xâu $s$.

Output:

• In ra số lượng kí tự tối thiểu cần thêm vào.

Sample Input:

2
teen
aadcbcab

Sample Output:

3
4

Ý tưởng

Gọi $dp[i][j]$ là số thao tác tối thiểu để xóa đoạn $[i, j]$ của xâu $s$.

Xét đoạn $[i, j],$ ta có:

• Nếu như $s_i = s_j,$ thì ta xóa hết đoạn $[i + 1, j - 1],$ đồng thời ở thao tác xóa cuối cùng, ta gộp luôn hai kí tự $s_i, s_j$ vào hai đầu của xâu đối xứng cuối cùng và xóa chung. Vì thế:

  $$dp[i][j] = dp[i + 1][j - 1]$$

• Còn nếu $s_i \ne s_j,$ thì có thể tồn tại ba cách xóa:

  • Xóa đoạn $[i, j - 1]$ rồi mới xóa $s_j$.
  • Xóa đoạn $[i + 1, j]$ rồi mới xóa $s_i$.
  • Xóa một đoạn đối xứng liên tiếp $[i, k]$ rồi xóa đoạn $[k + 1, j]$.

  Ta rút ra công thức:

  $$dp[i][j] = \text{min}\big(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i][k] + dp[k + 1][j]\big); \forall k: i \le k < j$$

Về cơ sở quy hoạch động, ta có $dp[i][i] = 1$ - cần một thao tác để xóa các xâu con độ dài $1,$ và $dp[i][i + 1] = 1$ hoặc $0$ tùy thuộc vào $s_i$ có bằng $s_{i + 1}$ hay không. Kết quả cuối cùng tất nhiên là $dp[1][n]$.

Độ phức tạp: $O(n^3)$.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>
#define int long long using namespace std; const int INFTY = 1e9 + 7; void solution(string &s)
{ s = ' ' + s; int n = s.size() - 1; vector < vector < int > > dp(n + 1, vector < int >(n + 1, INFTY)); for (int i = 1; i <= n; ++i) { dp[i][i] = 1; if (i < n) dp[i][i + 1] = (s[i] == s[i + 1]) ? 1 : 2; } for (int len = 3; len <= n; ++len) { for (int i = 1; i <= n - len + 1; ++i) { int j = i + len - 1; if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]); for (int k = i; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } } cout << dp[1][n] << endl;
} main()
{ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ntest; cin >> ntest; while (ntest--) { string s; cin >> s; solution(s); } return 0;
}

Ngôn ngữ Python:

INFTY = 10**9 + 7 def solution(s): n = len(s) - 1 dp = [[INFTY] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): dp[i][i] = 1 if i < n: dp[i][i + 1] = 1 if s[i] == s[i + 1] else 2 for l in range(3, n + 1): for i in range(1, n - l + 2): j = i + l - 1 if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] else: dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]) for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]) print(dp[1][n]) if __name__ == '__main__': t = int(input()) for _ in range(t): s = ' ' + input() solution(s)

III. Tài liệu tham khảo

• https://vnoi.info/wiki/algo/dp/palindrome-problems.md
• https://vnoi.info/problems/list/?tag=52&page=1