2012S_1：维哥尼亚密码

洛谷：P1079
OJ：P5966

维吉尼亚密码解密原理：

  • 基本原理：
    • 维吉尼亚密码是一种多表代换加密方法，通过使用一个密钥，对明文中的每个字母进行不同的位移加密。
    • 解密时，需要使用相同的密钥，将密文字母反向位移，恢复原始明文字母。
  • 密钥的扩展与对齐：
    • 为了确保每个密文字母都有对应的密钥字母，需要将密钥扩展（重复）或截断，使其长度与密文相同。
  • 字符位移计算：
    • 密钥字符转位移量：
      • 大写字母 'A' 对应位移量 0，'B' 对应 1，以此类推，直到 'Z' 对应 25。
      • 小写字母同理，'a' 到 'z' 对应 0 到 25。
    • 解密操作：
      • 对于密文字母 s[i]，从其 ASCII 码中减去对应的位移量 j，得到解密后的字符。
  • 字母范围回绕处理：
    • 因为字母表是循环的，减去位移量后可能会超出字母表的范围，需要加上 26（字母表长度）进行回绕。
    • 例如，对于大写字母，如果 decrypted_char 小于 'A'，则 decrypted_char += 26;。
  • 非字母字符处理：
    • 对于非字母字符（如数字、符号），在解密过程中保持不变，直接复制到结果中。

算法逻辑重组与详细说明：

  1. 输入读取：
    • 读取密钥 k：
      • 使用 getline(cin, k); 从标准输入读取一行，作为密钥字符串。
    • 读取密文 s：
      • 使用 getline(cin, s); 从标准输入读取一行，作为需要解密的密文字符串。
  2. 密钥预处理：
    • 获取长度：
      • 计算密钥的长度 len1 = k.size();。
      • 计算密文的长度 len2 = s.size();。
    • 调整密钥长度：
      • 当密钥长度小于密文长度时：
        • 扩展密钥：
          • 计算需要重复密钥的次数 times = len2 / len1;。
          • 计算剩余需要补充的字符数 remainder = len2 % len1;。
          • 初始化一个空字符串 extended_key。
          • 通过循环，将密钥重复 times 次添加到 extended_key。
          • 将密钥的前 remainder 个字符添加到 extended_key。
          • 最终，k = extended_key;，使得密钥长度与密文长度相同。
      • 当密钥长度大于或等于密文长度时：
        • 截断密钥：
          • 直接截取密钥的前 len2 个字符，k = k.substr(0, len2);。
  3. 初始化解密结果字符串：
    • 调整结果字符串大小：
      • 使用 ans.resize(len2); 将结果字符串 ans 的长度调整为与密文长度相同，以便后续按索引赋值。
  4. 解密过程：
    • 遍历每个字符：
      • 使用 for (int i = 0; i < len2; i++) 遍历密文的每个字符。
      • 计算密钥字符对应的位移量 j：
        • 初始化 j = 0;。
        • 判断密钥字符是否为大写字母：
          • 如果 k[i] 在 'A' 和 'Z' 之间，j = k[i] - 'A';。
        • 判断密钥字符是否为小写字母：
          • 如果 k[i] 在 'a' 和 'z' 之间，j = k[i] - 'a';。
        • 如果密钥字符不是字母：
          • j 保持为 0，即不进行位移。
      • 对密文字母进行解密：
        • 计算解密后的字符 decrypted_char = s[i] - j;。
      • 处理字母范围的回绕（循环）：
        • 对于大写字母：
          • 如果 s[i] 在 'A' 和 'Z' 之间：
            • 如果 decrypted_char 小于 'A'，说明越过了字母表的开头，需要回绕：
              • decrypted_char += 26;。
        • 对于小写字母：
          • 如果 s[i] 在 'a' 和 'z' 之间：
            • 如果 decrypted_char 小于 'a'，同样需要回绕：
              • decrypted_char += 26;。
        • 非字母字符处理：
          • 如果 s[i] 不是字母字符，保持原样：
            • decrypted_char = s[i];。
      • 将解密后的字符存入结果字符串：
        • ans[i] = decrypted_char;。
  5. 输出解密结果：
    • 使用 cout << ans << endl; 将解密后的明文输出到标准输出。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-10-11 14:53:40
 * 最后修改: 2025-10-04 20:46:43
 * 文件描述: 2012年提高组第一题 维吉尼亚密码
****************************************************************/
#include <iostream>
#include <string>
using namespace std;

int main() {
    string k, s, ans;
    getline(cin, k);  // 读取整行密钥
    getline(cin, s);  // 读取整行密文
    int len1 = k.size();  // 密钥长度
    int len2 = s.size();  // 密文长度

    // 将密钥扩展或截断到与密文相同的长度
    if (len1 < len2) {
        int times = len2 / len1;
        int remainder = len2 % len1;
        string extended_key = "";
        for (int i = 0; i < times; i++){
             extended_key += k;
        }
        extended_key += k.substr(0, remainder);
        k = extended_key;
    } else {
        k = k.substr(0, len2);  // 如果密钥比密文长，则截断
    }
    ans.resize(len2);  // 将 ans 字符串调整到正确的大小
    for (int i = 0; i < len2; i++) {
        int j = 0;  // 初始化 j
        if (k[i] >= 'A' && k[i] <= 'Z')
            j = k[i] - 'A';
        else if (k[i] >= 'a' && k[i] <= 'z')
            j = k[i] - 'a';
        // 进行解密操作
        char decrypted_char = s[i] - j;
        // 处理大写字母的回绕
        if (s[i] >= 'A' && s[i] <= 'Z') {
            if (decrypted_char < 'A')
                decrypted_char += 26;
        }
        // 处理小写字母的回绕
        else if (s[i] >= 'a' && s[i] <= 'z') {
            if (decrypted_char < 'a')
                decrypted_char += 26;
        } else {
            // 如果不是字母字符，保持原样
            decrypted_char = s[i];
        }
        ans[i] = decrypted_char;  // 将解密后的字符赋值给 ans 字符串
    }
    cout << ans << endl;  // 输出解密后的明文
    return 0;
}
Previous Topic
Back to Lesson
Next Topic