UVA856 UVA856 Vigenère 密码
题目描述
几个世纪以来，大多数（甚至所有）已知的加密方法都只使用单一的密码字母表。例如，尤利乌斯·恺撒（Julius Caesar）使用过一种替换密码，将明文消息中的每个字母替换为字母表中向后推移三位的字母（即 `A` 变为 `D`，以此类推）。
$16$ 世纪的某个时候，一位名叫 Blaise de Vigenère 的法国外交官，在 Leon Alberti、Johannes Trithemius 和 Giovanni Porta 前期工作的基础上，完善了一种新型密码。其最重大的突破在于使用了多个密码字母表，这使得频率分析法（一种通过密文推导明文的技术）对其完全失效，从而令该密码在当时坚不可摧。
### 如何加密明文消息
加密的第一步是绘制一个 Vigenère 方阵：
```text
明文字母
| a b c d e f g h i j k l m n o p q r s t u v w x y z
------+----------------------------------------------------
1 (A) | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
2 (B) | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
3 (C) | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
4 (D) | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
5 (E) | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
6 (F) | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
7 (G) | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
8 (H) | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
9 (I) | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
------+----------------------------------------------------
密 10 (J) | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
码 11 (K) | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
字 12 (L) | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
母 13 (M) | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
表 ------+----------------------------------------------------
14 (N) | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
15 (O) | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
16 (P) | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
------+----------------------------------------------------
17 (Q) | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
18 (R) | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
19 (S) | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
20 (T) | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
21 (U) | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
------+----------------------------------------------------
22 (V) | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
23 (W) | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
24 (X) | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
25 (Y) | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
26 (Z) | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
```
接下来，必须选择加密时使用的多个密码字母表（即方阵中的行）。一种实用的方法是通过密钥来选择。例如，密钥 `MIUP` 选择了第 $13$、$9$、$21$ 和 $16$ 个密码字母表（参见方阵中带下划线的行）。
在最后一步，明文消息中的每个字母都根据对应的密码字母表进行加密。例如，假设明文消息是 `programming`，密钥是 `MIUP`。编码后的消息将是：
```text
明文 - p r o g r a m m i n g
密钥 - M I U P M I U P M I U
密文字母表 - 13 9 21 16 13 9 21 16 13 9 21
----------------------------------------------------------------
密文 - C A J W E J H C V W B
```
明文中的字母 `p` 使用第 $13$ 个密码字母表加密为字母 `C`。这个 `C` 来自 Vigenère 方阵中第 `p` 列与第 $13$ 行的交叉点。明文中的第二个字母 `r`，使用第 $9$ 个密码字母表加密为字母 `A`（查看第 `r` 列与第 $9$ 行的交叉点），以此类推。如有必要（如本例所示），密钥可以多次重复，以匹配明文消息的长度。
### 如何解密密文消息
解密消息需要知道用于加密明文的密钥。例如，假设密文是 `CAJWEJHCVWB`，密钥是 `MIUP`。
```text
密文 - C A J W E J H C V W B
密钥 - M I U P M I U P M I U
密文字母表 - 13 9 21 16 13 9 21 16 13 9 21
----------------------------------------------------------------
明文 - p r o g r a m m i n g
```
`MIUP` 对应的多个密码字母表依然是 13、9、21 和 16。获取每个明文字母的方法是：在当前密码字母表所在的行中找到对应的密文字母，然后查看该列顶部的字母。例如，明文中的字母 `p` 位于第 13 行（密码字母表）中密文字母 `C` 所在列的顶部。当最后一个密文字母被解密时，解密过程结束。
（本背景资料基于 Simon Singh 的《The Code Book》第 45-51 页编写。）
输入格式
输入将包含多行。每行包含一个使用 Vigenère 密码加密的消息（全大写字母）。关于每条消息的唯一已知信息是：解密后，它代表一个用文本拼写的 $3$ 位数字（例如：`oneoneone` 或 `zerozeroseven`）。
输出格式
每组输入的输出结果之间用一个空行分隔。
对于每一行，输出该密文所有可能的解密结果。例如，密文 `PQRPQRPQR` 在密钥为 `ACM` 时代表 `oneoneone`，但在密钥分别为 `ACMACMVTC` 和 `ACMACMWHT` 时，也代表 `oneonetwo` 或 `oneonesix`，以此类推。
每个解密结果单独占一行，如样例输出所示。`->` 符号左侧的文本是密钥（全大写），右侧是对应的明文 $3$ 位数字（全小写）。同一输入消息的解密结果之间不应有空行。
注意：输出必须按明文数字的数值降序排列（`nineninenine` > `ninenineeight` > ... > `zerozeroone` > `zerozerozero`）。