Tổng hợp chi tiết: Kĩ thuật xử lí xâu trong C++

Nội dung này trình bày cách nhận biết bài toán về xâu, các kĩ thuật phổ biến (đảo xâu, nén - giải nén, mã hóa theo ASCII, ép kiểu char↔int), kèm mã C++ mẫu đã được hiệu chỉnh.

1. Nhận biết khi nào là bài toán về xâu

Định nghĩa:
Bài toán xử lý xâu (string) là các bài toán mà dữ liệu chính là chuỗi ký tự (letters), chữ số, hoặc chuỗi đại diện cho các tập số — và ta cần thao tác trên các ký tự đó (đảo, so sánh, nén, phân tích, mã hóa...).

Các dấu hiệu nhận biết:

• Đầu vào/đầu ra là chuỗi (string), hoặc chuỗi chứa chữ số/ký tự.
• Các thao tác cần thực hiện là: đảo, so sánh ký tự, tìm/ghép phụ chuỗi (substring), đếm ký tự liên tiếp, mã hóa/giải mã.
• Ví dụ dạng bài: đảo xâu, kiểm tra palindrome (xâu đối xứng), nén theo RLE, giải nén, parse các chuỗi dạng "3a2b", chuyển mã ASCII theo nhóm, tách số từ chuỗi, v.v.

Các dạng bài phổ biến:

• Đảo xâu (reverse)
• Xâu đối xứng (palindrome)
• Nén / Giải nén (Run-Length Encoding - RLE)
• Mã hoá / Giải mã (ASCII groups, base conversions)
• Ép kiểu giữa char và int để xử lý chữ số

2. Một số kĩ thuật xử lí xâu (chi tiết)

A. Kĩ thuật đảo xâu (Reverse string)

Ý tưởng: Tạo một chuỗi mới bằng cách đọc từ cuối chuỗi gốc về đầu, hoặc thay đổi in-place.

Cách 1 — dùng hàm có sẵn reverse (STL):

string rever(string s){
    string t = s;
        reverse(t.begin(),t.end());
    return t;
}

• Độ phức tạp thời gian: O(n)
• Độ phức tạp không gian: O(n) (vì tạo bản sao t), có thể làm in-place để O(1) extra.

Cách 2 — duyệt ngược và ghép ký tự:

string rever(string s){
    string t = s;
        for(int i = s.size(); i >= 0; i--){
            t += s[i];
        }
    return t;
}

• Độ phức tạp: O(n) thời gian, O(n) không gian.
• Lưu ý: dùng reserve để giảm chi phí cấp phát.

B. Kĩ thuật nén xâu — Run-Length Encoding (RLE)

Nguyên lí: Thay mỗi nhóm ký tự giống nhau liên tiếp bằng <số-lần-lặp><ký-tự> (hoặc ngược lại tùy kiểu biểu diễn). Ví dụ: "AAAABBBCCDAA" → "4A3B2C1D2A".

Mã C++ chuẩn:

void nenxau(string s){
    int cnt = 0;
            for(int i = 0; i < s.size();i++){
                    if(i == 0 || s[i-1] == s[i] ){
                            cnt++;
                    }
                    else{
                        if(cnt > 1) cout << cnt ;
                                cout << s[i-1];
                                cnt = 1;
                    }
            }
    if(cnt > 1)cout << cnt;
    cout << s[s.size()-1];
}

Lưu ý / Biến thể:

• Một số bài chỉ ghi số khi >1 (ví dụ A4B3C2DA2 hoặc A4B3C2DA2), tùy mô tả đề bài.
• Nếu chỉ ghi 4A cho AAAA và giữ B đơn lẻ là B (không 1B), cần điều chỉnh mã.

Độ phức tạp: O(n) thời gian, O(n) không gian cho chuỗi kết quả.

C. Kĩ thuật giải nén xâu (từ biểu diễn RLE)

Ý tưởng: - Ta chia ~s[i]~ làm 2 trường hợp :

~s[i]~ là một chữ cái từ ‘a’ → ‘z’ khi đó ta chỉ cần đơn giản thêm vào xâu t.

~s[i]~ là một chữ số khi đó ta có 2 trường hợp sau:

nếu ~s[i]~ có 1 đơn vị ta chỉ cần kiểm tra chữ đằng sau nó có phải là kí tự không nếu có ta sẽ thêm kí tự đó vào xâu theo số lượng của chữ số đằng trước.(kiểm tra ~s[i+1]~).

nếu s[i] có nhiều hơn 1 đơn vị ta chỉ cần tạo một vòng while để lấy hết tất cả các đơn vị của nó , rồi cộng vào xâu theo một số mà ta có.(kiểm tra ~s[i+1]~)

Mã C++:

string giainen(string s){
    string t;
    for(int i = 0; i < s.size();i++){
         if('a' <= s[i] && s[i] <= 'z'){
            t += s[i];
         }
         else if('1' <= s[i] && s[i] <= '9'){
            int k = s[i] - '0';
            while(i+1 < s.size() && '1' <= s[i+1] && s[i+1] <= '9'){
                k = k * 10 + (s[i + 1] - '0');
                i++;
            }
            if(i+1 < s.size() && 'a' <= s[i+1] && s[i+1] <= 'z'){
                    char c = s[i+1];
                for(int j = 0; j < k;j++){
                    t += c;
                }
                i++;
            }
         }
    }
    return t;
}

D. Kĩ thuật mã hóa/giải mã theo ASCII nhóm

Mục tiêu: Ta có chuỗi các chữ số biểu diễn mã ASCII của ký tự (ví dụ 97 là 'a') khi đó ta có 2 "nhóm": bắt đầu bằng 9 (hai chữ số, ví dụ mã 97-99) hoặc 1 (ba chữ số, ví dụ 100-122). Dưới đây là cách giải mã an toàn.

Giải pháp an toàn:

• Duyệt chuỗi, nếu gặp '9' thì đọc 2 chữ số (nếu đủ), chuyển thành số -> char.
• Nếu gặp '1' thì đọc 3 chữ số (nếu đủ), chuyển thành số -> char.
• Kiểm tra phạm vi (97..122) nếu chỉ muốn a..z.

Mã C++ minh họa:

void mahoa(string s){
    for(int i= 0; i < s.size(); i++){
        int k = 0;
        if(s[i] == '9'){
            k = (s[i]-'0');
            k = k*10 + (s[i+1] - '0');
            i += 1;
            cout << char(k);
        }
        if(s[i] == '1'){
            k = (s[i] - '0');
            k =k*10 + (s[i+1] - '0');
            k =k*10 + (s[i+2] - '0');
            i += 2;
            cout << char(k);
        }
    }
}

E. Kĩ thuật ép kiểu giữa char và int

1) Từ char sang int (chữ số sang giá trị số): Khi cần tách các chữ số từ chuỗi và chuyển từng chữ số thành giá trị số:

for(int i = 0; i < s.size() ; i++){
     if('0' <= s[i] && s[i] <= '9'){
        a.push_back(s[i] - '0');
     }
 }

2) Từ int sang char (số 0-9 sang ký tự '0'-'9'):

for(int i = 0; i < s.size() ; i++){     
   if('0' <= s[i] && s[i] <= '9'){
         s[i] = a[k] +'0';
          k++;
    }
}

Lưu ý:

• Đảm bảo các giá trị a[k] nằm trong [0,9] trước khi cộng '0'.
• Nếu cần chuyển số lớn (ví dụ 23) thành hai ký tự '2', '3', phải tách chữ số.

3. Những lỗi thường gặp & mẹo debug

• Truy cập s[i-1] khi i == 0 → out-of-bounds. Luôn kiểm tra chỉ số trước khi truy xuất.
• Truy cập s[i+1] mà không kiểm tra i+1 < s.size() → undefined behavior. Kiểm tra biên trước.
• Dùng char âm khi dùng isalpha/isdigit: ép sang unsigned char trước khi gọi hàm <cctype>.
• Không reserve cho string khi lặp ghép nhiều lần → chậm do reallocation. Dùng reserve() nếu biết kích thước gần đúng.
• Không xử lý giá trị lớn khi parse số nhiều chữ số → nên dùng long long nếu cần.
• Xác định rõ format đầu vào (ví dụ RLE có ghi 1A hay chỉ A cho ký tự duy nhất) — khác nhau giữa đề bài.