[NOIP 2009 提高组] 潜伏者

知识点

字符映射、双射检查、字符串

解题思路

扫描已知密文、明文的对应字符，维护密文到明文及明文到密文两个表。若任一旧映射与当前对应矛盾即Failed。扫描完必须覆盖全部26种字母，之后用解密表翻译待译电报。

正确性说明

两个方向的唯一映射同时成立等价于一一对应；完全覆盖26个字母后得到确定双射，逐字查表就是原文。若冲突或缺字母，则满足题意的完整破译未完成，按要求失败。

易错点

第一行是密文，第二行是明文，方向别反；即使待译电报只用少数字母，也要求已知信息覆盖26种。

复杂度

时间O(L)，空间O(26)加字符串输入。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){string a,b,c;cin>>a>>b>>c;int f[26],g[26];fill(f,f+26,-1);fill(g,g+26,-1);for(int i=0;i<(int)a.size();i++){int x=a[i]-'A',y=b[i]-'A';if((f[x]>=0&&f[x]!=y)||(g[y]>=0&&g[y]!=x)){cout<<"Failed\n";return 0;}f[x]=y;g[y]=x;}for(int i=0;i<26;i++)if(f[i]<0||g[i]<0){cout<<"Failed\n";return 0;}for(char x:c)cout<<char('A'+f[x-'A']);cout<<'\n';}