Đề bài

Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome. Ví dụ: xâu bobseesanna có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:

• bobseesanna = bob + sees + anna
• bobseesanna = bob + s + ee + s + anna
• bobseesanna = b +o + b + sees + a + n + n + a.

Cho xâu ký tự $S$, cần tìm cách biểu diễn xâu dưới dạng một dãy gồm số ít nhất các palindrome. Ví dụ: cho bobseesanna, do ta có bobseesanna = bob + sees + anna và không thể biểu diễn bobseesanna bởi ít hơn là palindrome nên biểu diễn này chính là biểu diễn cần tìm.

Dữ liệu vào:

• Gồm một dòng chứa xâu ký tự chỉ gồm các chữ cái latin thường.

Dữ liệu ra:

• Gồm một dòng duy nhất ghi số lượng ít nhất các palindrome trong biểu diễn tìm được.

Ví dụ:

// Input

bobseesanna

// Output

3

Giới hạn:

• Độ dài xâu $S$ không quá $1000$ ký tự.

Nhận xét:

• Như trong bài trước, ta sử dụng công thức QHĐ và hàm kiểm tra palindrome để giải quyết bài toán. Tuy nhiên, với việc độ dài xâu $s$ lớn hơn cỡ $1000$ kí tự, ta cần tìm một thuật kiểm tra palindrome hiệu quả hơn (làm giảm số vòng lặp lồng nhau).
• Ta thấy mỗi xâu palindrome có thể chia ra làm hai loại:
  • Loại 1: Xâu palindrome có "tâm" là $1$ kí tự, ví dụ: "aba", "acbca", "sbobs". Xâu "aba" có tâm là "b", xâu "acbca" có tâm là "b".
  • Loại 2: Xâu palindrome có "tâm" là $2$ kí tự, ví dụ: "baab", "cc", "rbaabr", "hotavnnvatoh". Xâu "baab" có tâm là "aa", xâu "cc" có tâm là "cc".
• Các palindrome đều có các kí tự con đối xứng nhau qua tâm của chúng, ví dụ như xâu "hotavnnvatoh" có tâm là "nn", kí tự "v", "a", "t", "o", "h", đều có các kí tự giống chúng ở phía bên kia tâm đối xứng.
• Bằng nhẫn xét trên, ta có thể thiết lập một mảng hai chiều kiểu bool có chỉ số $(i,j)$ thể hiện rằng liệu tổng của các kí tự từ $i$ tới $j$ có là palindrome không, điều kiện để tổng các kí tự từ $i$ đến $j$ là một palindrome là tổng các kí tự từ $i + 1$ đến $j - 1$ là palindrome và kí tự thứ $j$ và kí tự thứ $i$ phải bằng nhau.

Xây dựng mảng kiểm tra:

for (int i = 1; i<=n; i++) {
        palin[i][i] = true;
        int left = i - 1, right = i + 1;
        while (left != 0 && right != n + 1) //Điều kiện đảm bảo left và right không bị chệch ra khỏi xâu
        if (s[left] == s[right]) { 
            palin[left][right] = true;
            left--;
            right++;
        }
        else break;
        if (s[i] == s[i+1]) { //Điều kiện xâu phải có tâm là 2 kí tự
            palin[i][i+1] = true; //Hiển nhiên, tâm là một palindrome
            left = i - 1; 
            right = i + 2;
            while (left >= 1 && right <= n) { //Điều kiện đảm bảo left và right không bị chệch ra khỏi xâu
                if (s[left] == s[right]) { //Kiểm tra 2 kí tự, nếu bằng nhau thì ghi lại kết quả
                    palin[left][right] = true;
                    left--; //Nếu là palindrome thì ta xét tiếp các xâu to hơn
                    right++;
                } else break; //Nếu không bằng nhau tức là tổng các kí tự từ left tới right không phải palindrome, kết thúc vòng lặp bởi                  //nếu xét xâu sau thì điều kiện không được thoả mãn 
            }

        }
    }

Giải thích:

• Mảng hai chiều $palind(i,j)$ ghi lại kết quả kiểm tra xem tổng các kí tự từ $i$ tới $j$ có phải palindrome không, nếu là palindrome thì trả về $true$, nếu không thì trả về $false$.

• Sau khi đã xây dựng được mảng kiểm tra, ta chỉ cần lắp lại vào thuật toán cũ là xong.

  Full code:

  #include <bits/stdc++.h>
  using namespace std;
  char s[1005];
  bool palin[1001][1001];
  int f[1001];
  int n;
  int main()
  {
  
  scanf("%s", s + 1); //Đọc dữ liệu vào mảng char, bắt đầu từ 1
  n = strlen(s + 1); //Lấy độ dài của mảng, tính từ 1
  f[1] = 1;
  for (int i = 1; i<=n; i++) {
      palin[i][i] = true;
      int left = i - 1, right = i + 1;
      while (left != 0 && right != n + 1)
      if (s[left] == s[right]) {
          palin[left][right] = true;
          left--;
          right++;
      }
      else break;
      if (s[i] == s[i+1]) {
          palin[i][i+1] = true;
          left = i - 1;
          right = i + 2;
          while (left >= 1 && right <= n) {
              if (s[left] == s[right]) {
                  palin[left][right] = true;
                  left--;
                  right++;
              } else break;
          }
  
      }
  }
  
  for (int i = 2; i<=n; i++) {
      f[i] = f[i-1] + 1;
      for (int j = i-1; j>= 1; j--)
          if (palin[j][i] == true)
              f[i] = min(f[i], f[j-1] + 1);
  }
  cout << f[n];
  return 0;
  }

Nguồn bài tập: Chuyên Hoàng Văn Thụ Online Judge

Thiết kế thuật giải