Giả sử có một chuỗi đầu vào, một phân chia của chuỗi đó gọi là phân chia đối xứng (palindrome partitioning) khi mọi chuỗi con của phân chia đều là xâu đối xứng (palindrome). Ta phải tìm số lượng cắt tối thiểu để phân chia chuỗi thành các xâu đối xứng. Ví dụ chuỗi "ababbbabbababa" cần 3 cắt. Các xâu đối xứng: a | babbbab | b | ababa
Để giải quyết, ta làm theo các bước:
- n := độ dài chuỗi
- định nghĩa ma trận cut và pal kích thước n x n
- for i := 0 to n
- pal[i, i] := true và cut[i, i] := 0
- for len từ 2 đến n
- for i từ 0 đến n – len
- j := i + len – 1
- nếu len = 2, nếu str[i] = str[j], pal[i, j] := true
- ngược lại nếu str[i] = str[j] và pal[i+1, j-1] ≠ 0, pal[i, j] := true
- nếu pal[i, j] true, cut[i, j] := 0
- ngược lại
- cut[i, j] := ∞
- for k từ i đến j-1
- cut[i, j] := min(cut[i, j], cut[i, k] + cut[k+1, j+1] + 1)
- for i từ 0 đến n – len
- return cut[0, n-1]
Hãy xem triển khai sau:
Ví dụ
#include <iostream> #include <climits> using namespace std; int min (int a, int b){ return (a < b)? a : b; } int minPalPartion(string str){ int n = str.size(); int cut[n][n]; bool pal[n][n]; //true khi chuỗi con i đến j là đối xứng for (int i=0; i<n; i++){ pal[i][i] = true; //chuỗi con độ dài 1 là đối xứng cut[i][i] = 0; } for (int len=2; len<=n; len++){ for (int i=0; i<n-len+1; i++){//tìm tất cả chuỗi con độ dài len int j = i+len-1; // Chỉ số kết thúc if (len == 2) //chuỗi 2 ký tự pal[i][j] = (str[i] == str[j]); else //chuỗi hơn 2 ký tự pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1]; if (pal[i][j] == true) cut[i][j] = 0; else{ cut[i][j] = INT_MAX; //ban đầu đặt vô cực for (int k=i; k<=j-1; k++) cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1); } } } return cut[0][n-1]; } int main(){ string str= "ababbbabbababa"; cout << "Số cắt tối thiểu cho phân chia đối xứng: "<<minPalPartion(str); }Input
ababbbabbababa
Output
Số cắt tối thiểu cho phân chia đối xứng: 3