我该如何解决＆QUOT;地穴射手＆QUOT;运动提出了＆QUOT;编程挑战（程序设计竞赛培训手册）QUOT;？ [英] How do I resolve the "Crypt Kicker" exercise proposed in "Programming Challenges (The Programming Contest Training Manual)"?

问题描述

编程挑战（程序设计竞赛培训手册）可能是最好的一个在算法的练习书。 我已经解决了前11的练习，但现在我坚持地穴踢球者的问题：

"Programming Challenges (The Programming Contest Training Manual)" is probably one of the nicest exercises book on algorithms. I've resolved the first 11 exercises, but now I am stuck with "Crypt Kicker" problem:

地穴射手
  加密文本的共同但有不安全的方法是重排的英文字母。   换句话说，字母表中的每个字母始终替换一些其他信的文本。以确保该加密是可逆的，没有任何两个字母用相同的字母代替。

Crypt Kicker
A common but insecure method of encrypting text is to permute the letters of the alphabet. In other words, each letter of the alphabet is consistently replaced in the text by some other letter. To ensure that the encryption is reversible, no two letters are replaced by the same letter.

你的任务是解密几个EN codeD文本行，假设每个行使用一组不同的替代物，而且在解密的文本中的所有单词都从已知单词的字典。

Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

输入
  输入包括一行包含整数n，后跟n小写的话，每行一个，按字母顺序排列的。这些n个字组成可能会出现在解密文字的字典。
  继字典有几行输入。每一行被加密如上所述。

Input
The input consists of a line containing an integer n, followed by n lowercase words, one per line, in alphabetical order. These n words compose the dictionary of words which may appear in the decrypted text.
Following the dictionary are several lines of input. Each line is encrypted as described above.

有不超过1000字在字典中。无字超过16   字母。加密的行包含小写字母和空格   不超过长度为80个字符。

There are no more than 1,000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

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

Output
Decrypt each line and print it to standard output. If there are multiple solutions, any one will do.
If there is no solution, replace every letter of the alphabet by an asterisk.

采样输入的6
    和
    迪克
    简
    粉扑
    现货
    yertle

Sample Input 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

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

示例输出的
   迪克和简吞吐和现货和yertle ...

Sample Output
dick and jane and puff and spot and yertle ...

什么的策略的，我应该采取以解决这项工作？我当时就想，经典而野蛮回溯的解决方案，但我想避免这种情况，直到我找到更聪明。

What strategy should I to take in order to resolve this exercise? I was thinking to a classic and brutish backtracking solution, but I am trying avoid that until I find something more intelligent.

PS：这不是功课有关，我只是想提高我的整体技能

PS: This is not homework related, I am just trying to improve my overall skills.

推荐答案

KeyArray将持有的置换表。

KeyArray will hold the replacement table.

• 先建立一个空KeyArray，这是版本0

• Start with an empty KeyArray, this is version 0

匹配最长的加密字来最长的字典中的单词，并加入到KeyArray （如果有两个最长，挑选任何），这是版本1

Match longest encrypted word to longest dictionary word and add to KeyArray (if there are two longest, pick any), this is version 1.

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

Decrypt some letters of the next longest crypted word.

如果一些字母匹配，添加字母KeyArray的休息，这是第2版。

If some letters match, add the rest of the letters to KeyArray, this is version 2.

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

Decrypt some letters of the next longest crypted word.

重复，直到所有的单词进行解密。

Repeat until all words are decrypted.

如果在版本0无时间最长的单词创建了部分解密 较短的话，很有可能没有办法解决。

If at version 0 none of the longest words creates a partial decrypt in shorter words, very probably there is no solution.

这篇关于我该如何解决＆QUOT;地穴射手＆QUOT;运动提出了＆QUOT;编程挑战（程序设计竞赛培训手册）QUOT;？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！