Bài 2 (6.0 điểm): PALIN Một xâu S được gọi là xâu đối xứng nếu S = S' với S' là xâu nhận được từ xâu S khi đọc từ phải qua trái. Ví dụ: Xâu 'aba' là xâu đối xứng, còn xâu 'abc' là xâu không đối xứng. Cho một xâu S gồm n kí tự (1 n 100) Yêu cầu: Hãy tìm cách chia xâu S thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng. Dữ liệu vào: Từ file văn bản PALIN.INP gồm: - Dòng đầu gồm một số nguyên n là độ dài của xâu S. - Dòng thứ hai là nội dung xâu S. Kết quả: Ghi ra file văn bản PALIN.OUT gồm: - Dòng đầu ghi một số nguyên k (số đoạn ít nhất tìm được). - K dòng sau, mỗi dòng ghi một số nguyên ti, với ti là vị trí kết thúc của đoạn thứ i. Ví dụ: PALIN.INp 8 abbacdcb PALIN.out 3 4 7 8

#include <bits/stdc++.h>

using namespace std;
bool ktra(const string& s, int a, int b) {
    while (a < b) {
        if (s[a] != s[b]) {
            return false;
        }
        a++;
        b--;
    }
    return true;
}
int main() {
    long long n , ans = 1000000001 ; 
    cin >> n;
    string s;
    cin >> s;
    long long a[n + 1] , b[n + 1] , c = n , res[n] , cnt = 0;
    a[0] = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = ans;
        for (int j = 0; j < i; ++j) {
            if (ktra(s, j, i - 1) && a[j] != ans) {
                if (a[i] > a[j] + 1) {
                    a[i] = a[j] + 1;
                    b[i] = j + 1;
                }
            }
        }
    }
    cout << a[n] << endl;
    while (c > 0) {
        res[cnt++] = c;
        c = b[c] - 1;
    }
    for (int i = cnt - 1; i >= 0; --i) {
        cout << res[i] << endl;
    }
    return 0;
}