凯撒密码 题解

题目分析

本题要求根据一组已知的明文与密文，推算出凯撒密码的偏移量，并利用该偏移量解密另一段密文，得到对应的明文。

关键词：凯撒密码、字母偏移、取模运算、字符串处理。

已知条件：

• 第一行：明文 s1
• 第二行：密文 s2（由 s1 加密得到）
• 第三行：待解密的密文 s3（与 s1→s2 使用相同的偏移量加密）

要求： 输出 s3 解密后的明文。

限制： 所有字符串只包含大写字母 A~Z，长度不超过 1000。

---

解题思路

1. 理解凯撒密码的偏移规则

大写字母可以映射到数字 0 ~ 25（A=0, B=1, …, Z=25）。

• 加密：密文字母 = (明文字母 + offset) mod 26
• 解密：明文字母 = (密文字母 - offset + 26) mod 26 （或等价的循环移位）

其中 offset 是固定的整数，代表字母表向后移动的位数。

2. 利用已知明文和密文求偏移量

从第一对已知的明文字符 s1[0] 和密文字符 s2[0] 可以计算偏移量。

加密方向： s2[0] = (s1[0] + offset) mod 26
⇒ offset = (s2[0] - s1[0] + 26) % 26

不过我们也可以直接计算“解密时需要在密文上加多少才能得到明文”：
明文 = (密文 + diff) mod 26，其中 diff = (s1[0] - s2[0] + 26) % 26。
也就是说，diff 实际上是 -offset 在模 26 意义下的值，用它可以直接对密文进行解密。

代码中使用的就是这种方式：

cpp
复制
1int d = s1[0] - s2[0];
2d = (d % 26 + 26) % 26;

这样求出的 d 满足：
明文字母 = (密文字母 + d) % 26。

3. 解密待破解的密文

对 s3 中的每个字符 c，计算 (c - 'A' + d) % 26 得到明文对应的数字，再转换回大写字母输出即可。

---

算法说明

1. 读取三个字符串 s1, s2, s3。
2. 计算解密偏移量 d = (s1[0] - s2[0]) mod 26（保证结果为 0~25 之间的非负整数）。
3. 遍历字符串 s3 的每个字符 ch：
   • 将 ch 转换为数字：pos = ch - 'A'
   • 应用偏移：newPos = (pos + d) % 26
   • 转换回字符并输出：(char)(newPos + 'A')

由于所有字母都是大写，且偏移量恒定，该算法不会出现越界或非字母干扰。

---

时间复杂度分析

• 计算偏移量：O(1)
• 解密并输出 s3：O(n)，其中 n 为 s3 的长度，n ≤ 1000。

整体时间复杂度为 O(n)，空间复杂度为 O(1)（除了存储输入字符串外无额外开销）。在题目给定的数据范围下可以极快地运行。

---

参考代码解释

以下是完整的 C++ 参考代码，并附有详细注释：

cpp
复制
1#include <iostream>
2#include <string>   // 原代码中错写为 <cstring>，实际应为 <string>
3using namespace std;
4
5int main() {
6    string s1, s2, s3;
7    cin >> s1 >> s2 >> s3;
8
9    // 计算解密所需偏移量 d
10    // d = 明文 - 密文 (模26)
11    int d = s1[0] - s2[0];
12    d = (d % 26 + 26) % 26;   // 确保 d 在 0~25 之间
13
14    // 对密文 s3 逐字符解密
15    for (int i = 0; i < s3.length(); i++) {
16        int ch = (s3[i] - 'A' + d) % 26;   // 明文对应的数字
17        cout << (char)(ch + 'A');           // 转回大写字母输出
18    }
19
20    return 0;
21}

代码说明：

• 头文件 <string> 需正确引入，以便使用 string 类型。
• (d % 26 + 26) % 26 将可能为负数的模运算结果映射到 [0, 25]，保证下标合法。
• 输出字符时，(char)(ch + 'A') 将 0~25 的数字转换为对应的大写字母。

样例验证：
输入：

A
D
WKLV

计算 d = 'A' - 'D' = -3，模 26 后 d = 23。
s3 解密：
W(22) → (22+23)%26 = 19 → T
K(10) → (10+23)%26 = 7 → H
L(11) → (11+23)%26 = 8 → I
V(21) → (21+23)%26 = 18 → S
输出 THIS，符合预期。

---

总结

本题考察对凯撒密码加解密原理的理解，以及模运算在字符循环处理中的应用。关键在于从已知明密文对中正确推导出偏移量，并注意模运算中负数的处理。代码实现简洁，适合作为字符串和取模运算的入门练习题。