题解：密码破译与翻译（替换密码验证+映射应用）

一、解题核心思路

本题本质是 替换密码的合法性校验 + 完整映射构建 + 密文翻译，核心约束是「原字母与密字的一一对应（单射+满射）」。解题需分3个关键步骤：

1. 构建映射关系：通过已知的「加密信息-原信息」对，建立「原字母→密字」和「密字→原字母」的双向映射（确保双向唯一）。
2. 验证映射合法性：
   • 无矛盾：同一原字母不能对应多个密字，同一密字不能对应多个原字母。
   • 全覆盖：26个大写字母必须全部出现在原信息中（即映射覆盖A-Z）。
3. 密文翻译：若映射合法且完整，用「密字→原字母」的映射翻译目标加密信息。

二、具体解题步骤

步骤1：初始化数据结构

用两个大小为26的数组存储双向映射（A-Z对应索引0-25）：

• plain_to_cipher[26]：原字母 → 密字（索引=原字母-'A'，值=密字）。
• cipher_to_plain[26]：密字 → 原字母（索引=密字-'A'，值=原字母）。 初始化数组值为'\0'，表示未建立映射。

步骤2：构建并验证双向映射

遍历已知的「加密信息（cipher_str）」和「原信息（plain_str）」的每一对字符：

• 设当前原字母为x，对应密字为y。
• 若x已存在映射（plain_to_cipher[x-'A'] != '\0'），但映射结果≠y → 矛盾，输出Failed。
• 若y已存在反向映射（cipher_to_plain[y-'A'] != '\0'），但反向映射结果≠x → 矛盾，输出Failed。
• 否则，建立双向映射：plain_to_cipher[x-'A'] = y，cipher_to_plain[y-'A'] = x。

步骤3：验证映射全覆盖

检查plain_to_cipher数组是否所有元素都不为'\0'（即A-Z所有原字母都有对应的密字）：

• 若存在任一元素为'\0' → 未覆盖所有字母，输出Failed。

步骤4：翻译目标加密信息

遍历目标加密信息（target_str）的每个字符c：

• 通过cipher_to_plain[c-'A']获取对应的原字母，拼接成翻译结果。
• 输出翻译结果。

三、完整代码实现

#include <iostream>
#include <string>
using namespace std;

int main() {
    string cipher_str, plain_str, target_str;
    cin >> cipher_str >> plain_str >> target_str;

    // 初始化双向映射数组（A-Z对应索引0-25，初始为'\0'表示未映射）
    char plain_to_cipher[26] = {0};  // 原字母 → 密字
    char cipher_to_plain[26] = {0};  // 密字 → 原字母

    int len = cipher_str.size();
    // 步骤1：构建并验证双向映射
    for (int i = 0; i < len; ++i) {
        char x = plain_str[i];    // 原字母
        char y = cipher_str[i];   // 对应的密字
        int x_idx = x - 'A';
        int y_idx = y - 'A';

        // 情况1：原字母x已映射，但映射的密字不是y → 矛盾
        if (plain_to_cipher[x_idx] != '\0') {
            if (plain_to_cipher[x_idx] != y) {
                cout << "Failed" << endl;
                return 0;
            }
        }
        // 情况2：密字y已映射，但映射的原字母不是x → 矛盾
        else if (cipher_to_plain[y_idx] != '\0') {
            cout << "Failed" << endl;
            return 0;
        }
        // 情况3：正常建立双向映射
        else {
            plain_to_cipher[x_idx] = y;
            cipher_to_plain[y_idx] = x;
        }
    }

    // 步骤2：验证映射是否覆盖所有26个字母
    for (int i = 0; i < 26; ++i) {
        if (plain_to_cipher[i] == '\0') {
            cout << "Failed" << endl;
            return 0;
        }
    }

    // 步骤3：翻译目标加密信息
    string result;
    for (char c : target_str) {
        int idx = c - 'A';
        result += cipher_to_plain[idx];
    }

    cout << result << endl;
    return 0;
}

四、代码解释

1. 映射数组设计：

   • 利用字母ASCII码与索引的对应关系（A→0，B→1，…，Z→25），数组访问效率为O(1)。
   • 双向映射确保「原字母→密字」和「密字→原字母」均唯一，避免矛盾。

2. 合法性校验细节：

   • 遍历过程中实时校验矛盾，发现问题立即输出Failed并终止程序，无需后续处理。
   • 全覆盖校验确保密码破译完整（题目要求所有26个字母都有映射才能翻译）。

3. 翻译过程：

   • 目标加密信息的每个字符通过反向映射数组直接获取原字母，时间复杂度O(L)（L为目标字符串长度），高效简洁。

五、样例验证

样例1：矛盾映射

• 输入：AA（加密）、AB（原信息）→ 原字母A→A，B→A。
• 校验：密字A已映射到A，再映射B→A时触发矛盾 → 输出Failed。

样例2：映射未全覆盖

• 输入：原信息为ABCDEFGHIJKLMNOPQRSTUVWXY（缺少Z）。
• 校验：plain_to_cipher[25]（Z对应的索引）为'\0' → 输出Failed。

样例3：合法映射

• 映射覆盖所有26个字母，且双向唯一 → 目标加密信息FLSO通过cipher_to_plain映射得到NOIP → 输出NOIP。

六、复杂度分析

• 时间复杂度：O(N + M)，其中N为已知加密信息长度，M为目标加密信息长度（均≤100，效率极高）。
• 空间复杂度：O(1)，仅使用两个固定大小为26的数组，无额外空间消耗。