cryptography - 如何破译未知的替换密码

Question

您将获得一个包含字符串列表(每行一个)的文件。对字符串进行排序，然后使用未知的替换密码进行加密(例如 a < c, b < r, c < d )。如何确定替换密码的映射是什么？未加密的字符串可以是任何语言。

我想知道这个问题是否难，我正在申请一个新的毕业生职位，我无法很好地解决这个问题，他在这个问题上和我呆了大约 45 分钟。

Answer 1

我想关键事实是字符串在加密之前已排序，因此您根本不必担心语言。

我想到的第一个解决方案只是创建一个强力回溯算法，但这可能不好。

我能想到的第二个解决方案是从文件中提取所有已知的关系，例如。这个文件:

xtw
yaw
yay

会告诉你x < y (因为 xtw < 偏航)和 w < y (因为 yaq < yay)。有了有向关系图之后，你只需要对这个图进行拓扑排序，你的解决方案就在那里。