Editorial for Mã hóa xâu


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1: ~k=1~
  • Sử dụng ~map~.

  • Đặt ~mp[a[i]] = b[i]~ với ~∀ i ∈ [0,25]~. Sau đó với ~s[i]~ in ra ~mp[s[i]]~.

  • ĐPT: ~O(n*log(26))~

Subtask 2: ~k,|s|≤2000~
  • Tạo map ~mp~ tương tự subtask 1, sau đó với mọi ~s[i]~ thì gán ~s[i] = mp[s[i]]~ ~k~ lần, sau đó in ra sâu ~s~.

  • ĐPT: ~O(n*k*log(26))~

Subtask 3: ~k≤10^5~
  • Nhận thấy, nếu làm như subtask 2, sẽ có trường hợp một kí tự bị duyệt nhiều lần, vậy nên tạo mảng ~f[x] = x~ với ~x~ là các kí tự từ a đến z. Gán ~f[x] = mp[f[x]]~ ~k~ lần. Với ~s[i]~ in ra ~f[s[i]]~.

  • ĐPT: ~O(n + k*26*log(26))~

Subtask 4: ~k≤10^9~
  • Việc for ~(1 → k)~ là không đủ nhanh. Nhận thấy nếu liên tục gán ~x = mp[x]~ thì sẽ xảy ra vòng lặp (khi ~x~ quay về kí tự ban đầu). Cải tiến: tạo vector ~c[i]~ là các phần tử trong "vòng lặp" của kí tự ~i~. Gọi ~sz~ là kích cỡ của vector ~c[i]~. Ta có: ~f[i] = c[i][k~ % ~sz]~.

  • ĐPT: ~O(n+26*log(26))~

Code tham khảo:
//lamleloi
namespace sub4
{
    vector<int> c[26];
    map<char,char> mp,f;
    void sol()
    {
        for(int i=0; i<26; i++) mp[a[i]] = b[i];
        for(int i=0; i<26; i++){
            c[i].push_back(i);
            char cur = mp['a'+i];
            while(cur-'a'!=i) {
                c[i].push_back(cur-'a');
                cur = mp[cur];
            }
        }
        for(int i=0; i<26; i++){
            int pos = k%(c[i].size());
            f['a'+i] = c[i][pos] + 'a';
        }
        for(int i=0; i<s.size(); i++) cout << f[s[i]];
    }
}