Hiểu bài toán

Bài toán yêu cầu tìm độ dài của từ đối xứng dài nhất trong một chuỗi văn bản. Từ đối xứng là từ mà khi đọc xuôi hay đọc ngược đều giống nhau. Đầu vào là một chuỗi văn bản có thể chứa nhiều từ, được ngăn cách bởi dấu cách. Đầu ra là một số nguyên thể hiện độ dài lớn nhất của các từ đối xứng tìm được. Nếu không có từ đối xứng nào, kết quả là 0.

Các cách tiếp cận

Cách Brute Force - Kiểm tra từng từ

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

int main() {
    freopen("doixung.inp", "r", stdin);
    freopen("doixung.out", "w", stdout);

    string s;
    int max_len = 0;

    // Đọc từng từ từ input stream
    while (cin >> s) {
        string reversed_s = s;
        reverse(reversed_s.begin(), reversed_s.end());

        if (s == reversed_s) {
            max_len = max(max_len, (int)s.length());
        }
    }

    cout << max_len;
    return 0;
}

• Time Complexity: O(N * L^2)
• Space Complexity: O(L)

Đây là cách tiếp cận trực quan nhất. Ta lần lượt đọc từng từ trong chuỗi văn bản. Với mỗi từ, ta tạo một bản sao và sử dụng hàm reverse để lật ngược nó lại. Sau đó, ta so sánh từ gốc với từ đã lật. Nếu chúng giống nhau, từ đó đối xứng và ta cập nhật độ dài lớn nhất. Phương pháp này dễ hiểu và dễ cài đặt. Độ phức tạp thời gian phụ thuộc vào tổng kích thước của văn bản và độ dài các từ, trong đó thao tác lật và so sánh một từ có độ dài L tốn O(L).

Cách Optimized Brute Force - Kiểm tra tại chỗ

#include <string>
#include <iostream>
#include <algorithm>

int main() {
    freopen("doixung.inp", "r", stdin);
    freopen("doixung.out", "w", stdout);

    std::string s;
    int longest = 0;

    while (std::cin >> s) {
        std::string s2 = s;
        std::reverse(s.begin(), s.end());
        if (s2 == s) {
            longest = std::max(static_cast<int>(s2.size()), longest);
        }
    }

    std::cout << longest;
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(L)

Đây là phiên bản tối ưu hơn một chút của cách tiếp cận Brute Force. Thay vì dùng hàm dx bên ngoài, mã nguồn được viết liền mạch. Tuy nhiên, logic vẫn giữ nguyên: đọc từ, lật ngược, so sánh. Việc tối ưu nằm ở việc sử dụng std::cin để tự động phân tách từ và std::reverse để kiểm tra. Độ phức tạp vẫn là O(N * L) vì mỗi từ được xử lý trong thời gian tuyến tính với độ dài của nó.

Cách Two-Pointer - Kiểm tra thủ công

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

// Hàm kiểm tra đối xứng sử dụng hai con trỏ
bool is_palindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) {
            return false;
        }
    }
    return true;
}

int main() {
    freopen("doixung.inp", "r", stdin);
    freopen("doixung.out", "w", stdout);

    string s;
    int res = 0;

    while (cin >> s) {
        if (is_palindrome(s)) {
            res = max(res, (int)s.length());
        }
    }

    cout << res;
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(1)

Cách tiếp cận này khác biệt ở chỗ không tạo bản sao của từ để lật mà sử dụng kỹ thuật 'hai con trỏ' (two-pointers). Ta duyệt từ đầu và cuối của từ đồng thời, so sánh các ký tự tương ứng. Nếu có sự không khớp, ta ngay lập tức biết từ đó không đối xứng. Phương pháp này có độ phức tạp không gian tốt hơn (O(1) thay vì O(L) do không cần cấp phát bộ nhớ cho chuỗi đảo ngược) và thường nhanh hơn trong thực tế vì tránh được overhead của việc tạo và so sánh chuỗi mới.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành hai phần chính: phân tách các từ từ chuỗi đầu vào và kiểm tra tính đối xứng của từng từ.
• Sử dụng std::stringstream hoặc std::cin là cách hiệu quả nhất để tự động tách các từ dựa trên dấu cách.
• Kiểm tra đối xứng có thể thực hiện bằng cách so sánh từ với bản sao bị đảo ngược hoặc bằng cách so sánh trực tiếp các ký tự đối xứng từ hai phía vào tâm.

Lỗi thường gặp

• Quên xử lý các ký tự đặc biệt hay dấu cách thừa, mặc dù cin thường bỏ qua chúng tự động.
• Sử dụng biến string ban đầu cho cả việc so sánh và lưu trữ bản sao đã bị lật mà không khôi phục lại, có thể gây lỗi logic nếu mã phức tạp hơn.
• Bỏ qua trường hợp văn bản rỗng hoặc chỉ chứa dấu cách, cần trả về 0.