我该如何解决《编程挑战（编程竞赛培训手册）》中所提出的“Crypt Kicker”练习？

Question

"Programming Challenges (The Programming Contest Training Manual)" 可能是关于算法最好的练习书之一。 我已经解决了前11个问题，但现在卡在了 "Crypt Kicker" 问题上：

Crypt Kicker
加密文本的一种常见但不安全的方法是对字母表中的字母进行置换。 换句话说，文本中的每个字母都被某个其他字母替换。 为确保加密是可逆的，不能将两个字母替换为同一个字母。

您的任务是解密多个编码行的文本，假设每行使用不同的替换集，并且所有解密后文本中的单词来自已知单词的字典。

输入
输入由包含整数n的一行组成，后跟按字母顺序排列的n个小写单词，每个单词占一行。这n个单词组成可能出现在解密文本中的单词字典。
字典之后是几行输入。 每行均按上述方式加密。

字典中不超过1000个单词。没有单词超过16个字母。加密的行仅包含小写字母和空格，长度不超过80个字符。

输出
解密每行并将其打印到标准输出。 如果有多个解决方案，则任何一个都可以。
如果没有解决方案，请用星号替换字母表中的每个字母。

示例输入 6
and
dick
jane
puff
spot
yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

示例输出
dick and jane and puff and spot and yertle ...

我该采取什么策略来解决这个问题？我考虑使用经典而粗暴的回溯解决方案，但我正在尝试避免这样做，直到我找到更加智能的方法。

PS：这不是作业相关，我只是想提高我的技能水平。

- Andrei Ciobanu

Answer 1

KeyArray将保存替换表。

• 从一个空的KeyArray开始，这是版本0。

• 将最长的加密单词与最长的字典单词匹配，并添加到KeyArray中（如果有两个最长的单词，则选择任意一个），这是版本1。

• 解密下一个最长的加密单词的一些字母。

• 检查解密后的字母是否与相同长度的任何字典单词中相同位置上的字母匹配。
• 如果没有匹配项，请返回版本0并尝试另一个单词。

• 如果有一些字母匹配，请将剩余的字母添加到KeyArray中，这是版本2。

• 解密下一个最长的加密单词的一些字母。

• 检查解密后的字母是否与任何字典单词中相同位置上的字母匹配。
• 如果没有匹配项，请返回版本1并尝试另一个单词。
• 如果有一些字母匹配，请将剩余的字母添加到KeyArray中，这是版本3。

重复以上步骤，直到所有单词都被解密。

如果在版本0中最长的单词没有创建更短单词的部分解密，则很可能没有解决方案。

- Carlos Gutiérrez

---

谢谢，我会看一下这种方法的！ - Andrei Ciobanu

我有一个类似的想法，但是从最小的单词开始而不是最长的单词。这样有什么区别吗？ - Maged Saeed

此外，这个算法的复杂度是多少？很可能是指数级的，不是吗？ - Maged Saeed

Answer 2

在回溯运行之前，可以通过枚举可能性来进行一些小的优化。在Python中：

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

输出：

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

如果您有一些单元素的可能性，可以将它们从输入中删除并重新运行算法。

编辑：改用集合而不是列表，并添加打印代码。

- Max Shawabkeh

---

谢谢，我会考虑那些优化！ - Andrei Ciobanu

当字典大小增加时，这将变得不那么有用，对吧？ - jk.

对于较大的输入，您最好按字母频率排序节点，并使用简单的深度优先搜索，就像Sylvestre的回答一样。 - Max Shawabkeh

Answer 3

我实际上尝试了一种不同的方法。我从字典单词中构建了一个trie树。然后我递归地遍历trie树和句子（使用深度优先搜索遍历trie树）。

在每个空格处，我确保我在trie树中找到了一个单词的结尾，如果是这样，我就回到根节点。沿途我会记录我已经做出的字母分配。如果我有任何与之前的分配相矛盾的分配，我就失败了，并解开递归，直到我可以做出下一个可能的分配。

听起来很棘手，但它似乎工作得非常好。而且编码起来并不那么难！

- superboggly

Answer 4

另一个可能的优化方法是，如果您有足够的文本处理并且知道文本的语言，则可以使用字母频率（参见：http://en.wikipedia.org/wiki/Letter_frequency）。当然，在处理6/7个单词时，这是一种非常粗略的方法，但如果您有几页要解码，这将是最快的方法。

编辑：关于Max的解决方案，您也可以尝试提取单词的一些特征，例如重复的字母。显然，注意到字典中的puff和加密文本中的qymm是仅以双字母结尾的四个字母单词，可以直接回答3个字母的问题。在更复杂的情况下，您应该能够缩小每个字母对的可能性。

- Sylvestre Equy

---

这很酷，因为夏洛克·福尔摩斯在《跳舞人的冒险》中使用了它 :) http://monpinillos.wordpress.com/2008/06/02/holmess-skills-cryptography/ - Carlos Gutiérrez

不幸的是，我必须生成足够的文本。但这本身就是一个很酷的问题：“生成加密文本”。感谢您的建议。 - Andrei Ciobanu

Answer 5

这里是一个Java实现，对@Carlos Gutiérrez提出的算法进行了更多的改进。

Crypt Kicker算法和解决方案，出了什么问题？

• 改进是添加单词模式以减少单词搜索空间。例如，单词“abc”和“her”具有相同的模式，而“aac”和“her”则不具有相同的模式，因为三个不同字母的单词不会匹配两个不同字母的单词。

• 此外，该算法可以递归实现，更加直观和合理。

- Maged Saeed