Hướng dẫn giải của [200 đề thầy Đức] Bài 125: Chuỗi con đối xứng


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Cho xâu $S$ gồm $n$ chữ cái in hoa, cần tìm độ dài của xâu con đối xứng dài nhất. Một xâu con là đoạn liên tiếp của $S$.

Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 100~

Thử mọi đoạn con $S[i..j]$. Với mỗi đoạn, so sánh hai đầu rồi đi vào trong để kiểm tra đối xứng. Giữ lại độ dài lớn nhất trong các đoạn đối xứng.

Kết quả chấm riêng sub này: đúng 20/20 test.

Sub 2: Mở rộng từ tâm — ~O(n^2)~

Mỗi xâu đối xứng đều có một tâm: hoặc là một ký tự (độ dài lẻ), hoặc là khoảng giữa hai ký tự kề nhau (độ dài chẵn). Với mỗi tâm, mở rộng hai đầu ra hai phía chừng nào hai ký tự còn bằng nhau. Độ dài đối xứng lớn nhất ứng với mỗi tâm là hiệu của hai chỉ số biên, và đáp án là giá trị lớn nhất trong các tâm.

Bẫy cần chú ý: phải xét cả tâm lẻ (một ký tự) lẫn tâm chẵn (hai ký tự kề nhau), vì xâu đối xứng có thể có độ dài chẵn. Ví dụ ABBA có tâm nằm giữa hai chữ B.

Kết quả chấm riêng sub này: đúng 20/20 test.

Chương trình hoàn chỉnh

Chương trình đọc $n$ và xâu $S$, rồi gọi sub1 nếu $n \le 100$, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

// Sub 1: vét cạn — thử mọi đoạn con s[i..j], kiểm tra đối xứng bằng cách so sánh hai đầu
// Độ phức tạp O(n^3). Dùng khi n <= 100
void sub1() {
    int best = 1;   // một ký tự luôn là đoạn đối xứng
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            bool pal = true;
            for (int a = i, b = j; a < b; a++, b--)
                if (s[a] != s[b]) { pal = false; break; }
            if (pal) best = max(best, j - i + 1);
        }
    cout << best << "\n";
}

// Sub 2: mở rộng từ tâm — mỗi tâm (ký tự hoặc khoảng giữa hai ký tự) mở rộng ra hai phía
// đến khi không còn đối xứng. Độ phức tạp O(n^2). Dùng cho mọi n <= 1000
void sub2() {
    int best = 1;
    for (int c = 0; c < n; c++) {
        // Tâm là một ký tự: độ dài lẻ
        int lo = c, hi = c;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) { lo--; hi++; }
        best = max(best, hi - lo - 1);
        // Tâm là khoảng giữa c và c+1: độ dài chẵn
        lo = c; hi = c + 1;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) { lo--; hi++; }
        best = max(best, hi - lo - 1);
    }
    cout << best << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    n = (int)s.size();   // phòng khi độ dài đọc được khác với n ghi trong đề
    if (n <= 100) sub1();   // n nhỏ: vét cạn cho chắc
    else sub2();            // n lớn: mở rộng từ tâm
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.