Hiểu bài toán

Bài toán yêu cầu giải mã một chuỗi đã được mã hóa bằng phương pháp Caesar. Trong mã hóa Caesar, mỗi ký tự trong bản gốc được thay thế bằng một ký tự khác trong bảng chữ cái, nằm về phía trước một khoảng k vị trí. Ví dụ, với k = 3, 'a' mã hóa thành 'd', 'b' thành 'e', ..., 'z' thành 'c'. Đầu vào là chuỗi mã hóa và khóa k. Đầu ra cần là chuỗi bản gốc. Nói cách khác, ta cần thực hiện thao tác ngược lại: thay mỗi ký tự trong chuỗi mã hóa bằng ký tự đứng sau nó k vị trí trong bảng chữ cái (tương đương với dịch trái k vị trí trong bảng mã ASCII).

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

Cách Phép toán trừ và kiểm tra biên (Arithmetic Subtraction)

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

int main(){
   string s;
   int k;
   cin >> s >> k;
   for(int i = 0; i < (int)s.length(); ++i){
       s[i] -= k;
       if(s[i] < 97){
           s[i] += 26;
       }
       cout << s[i];
   }
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp và hiệu quả nhất. Ta lặp qua từng ký tự s[i] trong chuỗi mã hóa. Vì mã hóa là cộng k (vượt qua 'z' thì quay lại đầu bảng), giải mã là trừ k. Ta thực hiện s[i] -= k. Nếu kết quả nhỏ hơn mã ASCII của 'a' (97), điều đó có nghĩa là ký tự đã bị trượt ra khỏi bảng chữ cái (ví dụ: 'c' - 3 = '`'). Ta cần cộng thêm 26 để quay lại cuối bảng. Ví dụ: 'd' (100) - 7 = 93 < 97 => 93 + 26 = 119 ('w').

Cách Sử dụng công thức toán học Modulo

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

int main() { 
    string s;
    int k;
    cin >> s >> k;
    for(char x : s) {
        char tmp;
        tmp = (((x - k - 97) % 26 + 26) % 26) + 97;
        cout << tmp;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách này sử dụng công thức chuẩn để chuẩn hóa số học modulo. Ta chuẩn hóa ký tự về dải [0, 25] bằng cách trừ đi 'a' (97), sau đó trừ k. Phép chia lấy dư % 26 có thể trả về số âm trong C++, nên ta cộng thêm 26 và lấy dư lần nữa để đảm bảo kết quả luôn nằm trong [0, 25]. Cuối cùng cộng lại 'a' để trở về ký tự. Ví dụ: 'd' (100) - 'a' (97) - k = 3 - 7 = -4. (-4 % 26 + 26) % 26 = 22. 22 + 'a' = 'w'.

Cách Sử dụng bảng tra cứu (Lookup Table)

#include <iostream>
using namespace std;
string latin = "abcdefghijklmnopqrstuvwxyz";

int find(string &s, const char &c) {
    for (size_t i = 0; i < s.length(); i++) {
        if (s[i] == c) return i;
    }
    return 0;
}

string decrypt(string s, int &key) {
    if (s.empty()) return s;
    int n = s.length(); key %= n;
    size_t j;
    string charset = "abcdefghijklmnopqrstuvwxyz";
    string script = "";
    charset = charset.substr(key) + charset.substr(0, key);
    for (size_t i = 0; i< s.length(); i++) {
        j = find(charset, s[i]);
        script += latin[j];
    }
    return script;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    string s; cin >> s >> n;
    s = decrypt(s, n);
    cout << s << endl;
    return 0;
}

• Time Complexity: O(26 * n)
• Space Complexity: O(1)

Phương pháp này tạo một bảng ký tự mã hóa charset bằng cách xoay chuỗi 'abc...z' theo khóa k. Sau đó, với mỗi ký tự trong chuỗi đầu vào, nó tìm vị trí của ký tự đó trong charset (bằng vòng lặp duyệt qua 26 ký tự), và lấy ký tự tương ứng tại cùng vị trí đó trong bảng latin chuẩn. Cách này hoạt động đúng nhưng kém hiệu quả do phải thực hiện tìm kiếm tuyến tính cho mỗi ký tự.

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

Bài học kinh nghiệm

• Mã hóa Caesar là phép cộng dồn (addition modulo 26), do đó giải mã là phép trừ dồn (subtraction modulo 26).
• Dãy số ASCII của các chữ cái thường ('a' đến 'z') liên tiếp, cho phép thực hiện các phép toán số học trực tiếp lên mã ASCII của ký tự.
• Cần xử lý trường hợp âm khi thực hiện phép trừ (trường hợp 'a' - k < 'a') bằng cách cộng thêm 26 hoặc sử dụng phép toán modulo.

Lỗi thường gặp

• Quên xử lý tràn số khi trừ k (ví dụ: mã ASCII của 'a' hoặc 'b' bị trừ đi một k lớn sẽ thành ký tự đặc biệt).
• Lầm tưởng rằng k luôn nhỏ hơn độ dài chuỗi đầu vào, trong khi k là khoảng cách trong bảng chữ cái.
• Sử dụng char hoặc int không đúng chuẩn để lưu trữ mã ASCII, có thể gặp vấn đề về dấu (signed/unsigned) khi tính toán.