🔗 UVA-828 Deciphering Messages

tags: `字串(String)` `集合(Set)` `模擬(Simulation)`

範例程式碼已於 UVA、瘋狂程設(CPE) 上皆測試通過。

題意

題目描述了一種加密方法，並要求解碼使用此方法加密的訊息。加密方法中使用了一個字元集合 $L$ 做為 字母密鑰(alphabet key) ，以字串的形式給出；以及一個在 $[1, 25]$ 間的整數 $N$ ，做為 數字密鑰(numerical key)。給定 $q$ 行加密訊息 $s$ ，請 分別解密 每行加密訊息。

加密方法的規則如下：

從左到右逐個字母分別加密，字母之間的空格保留。
如果字母 $p$ 不在字母密鑰 $L$ 中，則將其轉換為 $ciph(p)$ ，這個函數將字元 $p$ 按數字密鑰 $N$ 向後循環移動 $N$ 個位置。
如果字母 $p$ 在字母密鑰 $L$ 中，則將其轉換為三個字母：字母密鑰 $L$ 中的第 $m$ 個字母，接著是 $ciph(p)$ ，再接著是字母密鑰 $L$ 中的第 $m+1$ 個字母。每次應用此規則時 $m$ 增加 $1$ ，並且字母密鑰 $L$ 是循環的。

解密程式需要處理多個測試案例，每個案例包括多行加密後的訊息，需要輸出解碼後的原始訊息。

思路：模擬(Simulation)

由於加密時是向右移動 $N$ 個位置，所以解密時就是向左移動 $N$ 個位置。我們可以先定義一個 rotateLeft 函數，用來根據數字密鑰 N 對字元向左循環移動。

再來根據加密的規則逐個字元解碼，為此我們使用一個指針 $i$ 指向加密訊息的當前位置，另一個指針 $m$ 指向字母密鑰 $L$ 的當前位置，並將答案保存到字串 $ans$ 中。根據規則逐個字元解碼，並根據規則更新指針 $i$ 和 $m$ 。

根據規則一，如果遇到空格，則不會被加密，直接將其加入答案中，並移動指針 $i$ 。
根據規則三，如果遇到的字元是字母密鑰 $L$ 中的第 $m$ 個字母，且下下一個字元是字母密鑰 $L$ 中的第 $m+1$ 個字母，則將下一個字元根據數字密鑰 $N$ 向左循環移動得出原始字元 $ori$ 。若 $ori \notin L$ ，則表示原始字元不在字母密鑰 $L$ 中，與加密規則衝突，需要輸出 error in encryption；否則將其加入答案中，並移動指針 $i$ 和 $m$ 。
根據規則二，對於剩下的情況，直接將遇到的字元根據數字密鑰 $N$ 向左循環移動得出原始字元 $ori$ 。若 $ori \in L$ ，則表示原始字元在字母密鑰 $L$ 中，與加密規則衝突，需要輸出 error in encryption；否則將其加入答案中，並移動指針 $i$ 。

之所以先檢查規則三，是因為規則三的條件比較特殊。但由於我不確定解密時規則三是否會與規則二互斥，因此在使用規則三解密會發生衝突時，仍然先檢查是否會可以使用規則二解密。不過事實上，移除這部分的二次檢查也能通過測試。

複雜度分析

時間複雜度： $O(n)$ ， $n$ 為加密訊息的長度。
空間複雜度： $O(n)$ ，需要一個字串 $ans$ 保存解密後的訊息。

def rotateLeft(ch: str, N: int): # rotate left N times
    return chr(ord('A') + (ord(ch) - ord('A') - N) % 26)

t = int(input())
for kase in range(t):
    input() # skip blank line
    if kase > 0: # print a blank line between test cases
        print()
    
    L = input()
    N = int(input())
    q = int(input())
    st = set(L)

    for _ in range(q):
        s = input()
        i = m = 0
        ans = ""

        while (i < len(s)):
            ch = s[i]
            if ch == " ": # Rule 1
                ans += ch
                i += 1
            elif i + 2 < len(s) and ch == L[m] and s[i+2] == L[(m+1) % len(L)]: # Rule 3
                ori = rotateLeft(s[i+1], N)
                if ori not in st: # original charater should in L
                    ori = rotateLeft(ch, N) # Rule 2
                    if ori in st: # original charater should not in L
                        print("error in encryption")
                        break
                    ans += ori
                    i += 1
                    continue
                ans += ori
                i += 3
                m = (m + 1) % len(L)
            else: # Rule 2
                ori = rotateLeft(ch, N)
                if ori in st: # original charater should not in L
                    print("error in encryption")
                    break
                ans += ori
                i += 1
        else:
            print(ans)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

char rotateLeft(char ch, int N) { // rotate left N times
    return ('A' + (ch - 'A' - N + 26) % 26);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, N, q, kase = 0;
    string L, s, ans;
    cin >> t;
    cin.ignore(); // skip rest of line
    while (t--) { 
        cin.ignore(1024, '\n'); // skip blank line
        if (kase++) cout << endl;
        getline(cin, L);
        cin >> N >> q;
        cin.ignore(); // skip rest of line
        set<char> st(L.begin(), L.end()); // store all characters in L
        while (q--) {
            getline(cin, s); // encrypted string
            int i = 0, m = 0;
            ans = "";
            bool flag = true;
            while (i < s.size()) {
                char ch = s[i];
                // Rule 1
                if (ch == ' ') {
                    ans += ch;
                    i++;
                    continue;
                }
                // Rule 3
                else if (i + 2 < s.size() && ch == L[m] && s[i+2] == L[(m+1) % L.size()]) {
                    char ori = rotateLeft(s[i+1], N); // original character
                    if (!st.count(ori)) { // not satisfy Rule 3
                        // Rule 2
                        ori = rotateLeft(ch, N); // original character
                        if (st.count(ori)) { // also not satisfy Rule 2
                            flag = false;
                            break;
                        }
                        ans += ori;
                        i++;
                        continue;
                    }
                    ans += ori;
                    i += 3;
                    m = (m + 1) % L.size();
                // Rule 2
                } else {
                    char ori = rotateLeft(ch, N); // original character
                    if (st.count(ori)) { // not satisfy Rule 2
                        flag = false;
                        break;
                    }
                    ans += ori;
                    i++;
                }
            }
            cout << (flag ? ans : "error in encryption") << endl;
        }
    }
    return 0;
}