时间戳

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

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

问题描述

问题描述：

Crypt kicker 算法是一种众所周知的加密算法，但安全性较低。这个UVa问题就是基于这种方法解密行。问题陈述如下：

第843章

加密文本的一种常见但不安全的方法是排列字母表中的字母。也就是说，在文本中，字母表中的每个字母都被其他字母一致地替换。为了保证加密是可逆的，没有两个字母被同一个字母代替。你的任务是解密几行编码的文本，假设每一行使用一组不同的替换，并且解密文本中的所有单词都来自已知单词的字典。

输入

输入由包含整数 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

样本输出

迪克、简、吹、斑点和叫喊

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

什么地方出了错？

我创建了一个 Java 代码来解决它。我使用的算法如下图所示。代码似乎是正确的。它通过了我提供给它的所有测试用例，包括uDebug测试用例。但是，将我的代码提交给 UVA 在线法官时，它总是返回给我 WRONG ANSWER 判决！谁能找出我的问题？代码有隐藏的缺陷吗？还是网评的问题？！

非常感谢任何帮助！

算法说明：

解决这个问题的第一个想法是排列字母表中的所有字母以找到映射。然而，这个解决方案的计算量很大。一个更好的主意是使用回溯。您将加密词映射到与加密词具有相同长度和模式的字典词。[显示单词模式的含义：'abc'可能映射到'her'但是，它不能映射到'see'，因为模式不同“三个不同的字母词不能映射到两个不同的字母词”我拿了这个这个讨论的好主意]。如果您找到到第一个单词的映射，则移动到下一个单词并对其进行映射。如果第二个单词没有解决方案，则返回第一个单词并尝试另一个映射，依此类推。如果没有合适的映射到第一个单词，则声明没有解决方案。对于映射，我首先映射最长的单词，因为它们更难映射。

编码：

这是我的代码。我试图注释掉重要的行。但是，如果您发现任何困惑，请询问，我将详细解释。谢谢，

import java.util.*;

public class P843 {
public static void main(String[] args) {

    Scanner c = new Scanner(System.in);
    int dictionarySize = c.nextInt();
    c.nextLine();

    // get the dictionary from the input stream:
    String[] words = new String[dictionarySize];
    for (int i = 0; i < words.length; i++)
        words[i] = c.nextLine();

    // get encrypted input
    String line = c.nextLine();
    while (c.hasNextLine()) {
        if (line.length() == 0) {
            System.out.println();
            line = c.nextLine();
            continue;
        }
        ArrayList<String> eWordsList = new ArrayList<>();
        for(String eWord : line.split(" "))
            if(eWord.length() != 0)
                eWordsList.add(eWord);
        String[] eWords = eWordsList.toArray(new String[0]);

        String[] dWords = decryptWords(eWords, words);
        for (int i = 0; i < dWords.length; i++)
            if (i != dWords.length - 1)
                System.out.print(dWords[i] + " ");
            else
                System.out.println(dWords[i]);

        line = c.nextLine();

    }

}

private static String[] decryptWords(String[] eWords, String[] words) {

    String[] dWords = new String[eWords.length];

    // get copy of the dWords so that the original version not destroyed
    String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
    // sort by length from the greatest to the smallest
    Arrays.sort(eWordsCopy, new Comparator<String>() {
        @Override
        public int compare(String w1, String w2) {
            return Integer.compare(w2.length(), w1.length());
        }
    });

    // initialize a key array to hold decrypted letters:
    char[][] keyArray = new char[2][26];
    for (int i = 0; i < 26; i++) {
        keyArray[0][i] = (char) ('a' + i);
        keyArray[1][i] = '*';
    }


    // restore keyArray original values if there is no solution to all words
    if (!matchWords(words, eWordsCopy, keyArray))
        for (int i = 0; i < 26; i++) {
            keyArray[0][i] = (char) ('a' + i);
            keyArray[1][i] = '*';
        }
    for (int i = 0; i < eWords.length; i++) {
        StringBuilder temp = new StringBuilder();
        for (int j = 0; j < eWords[i].length(); j++)
            temp.append(keyArray[1][eWords[i].charAt(j) - 97]);
        dWords[i] = temp.toString();
    }
    return dWords;
}

private static boolean matchWords(String[] words, String[] eWords, char[][] keyArray) {
    ArrayList<String> promisingWords = new ArrayList<>();
    String eWord = eWords[0];

    // store the current state of keyArray
    char[][] originalKeyArray = new char[2][26];
    for (int i = 0; i < keyArray.length; i++)
        if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);
    // get promising words that may match
    for (String word : words)
        if (word.length() == eWord.length()
                && wordPattern(word).equals(wordPattern(eWord)))
            promisingWords.add(word);

    for (String word : promisingWords) {
        if (mapWord(eWord, word, keyArray)) {
            if (eWords.length > 1) {
                // recursive call:
                if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
                    return true;
                else {
                    // remove the word from the dictionary to try another one
                    for (int i = 0; i < keyArray.length; i++)
                        if (keyArray[i].length >= 0)
                            System.arraycopy(originalKeyArray[i], 0, keyArray[i], 0, keyArray[i].length);
                }
            }
            // if there are now decrypted words, then return true
            else
                return true;
        }
    }
    // if there is no word mapped, then return false
    return false;
}

private static boolean mapWord(String eWord, String word, char[][] keyArray) {
    // store the current state of keyArray
    char[][] originalKeyArray = new char[2][26];
    for (int i = 0; i < keyArray.length; i++)
        if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);

    // check one-to-one from the decrypted word to the dictionary word:
    for (int i = 0; i < eWord.length(); i++)
        if ((keyArray[1][eWord.charAt(i) - 97] != word.charAt(i)
                && keyArray[1][eWord.charAt(i) - 97] != '*')
                || !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
            // restore original array back
            for (int j = 0; j < keyArray.length; j++)
                if (keyArray[j].length >= 0)
                    System.arraycopy(originalKeyArray[j], 0, keyArray[j], 0, keyArray[j].length);
            return false;
        }

        // update the key array:
        else
            keyArray[1][eWord.charAt(i) - 97] = word.charAt(i);

    return true;
}

private static boolean isLetterMapped(char eLetter, char letter, char[][] keyArray) {
    for (int i = 0; i < 26; i++)
        if (keyArray[1][i] == letter && keyArray[0][i] != eLetter)
            return false;
    return true;
}

// generate a word pattern
private static String wordPattern(String word) {
    if (word.length() > 0) {
        StringBuilder mapped = new StringBuilder();
        int count = 0;
        HashMap<Character, Character> mapping = new HashMap<>();
        for (int i = 0; i < word.length(); i++)
            if (!mapping.containsKey(word.charAt(i)))
                mapping.put(word.charAt(i), (char) (48 + count++));
        for (int i = 0; i < word.length(); i++)
            mapped.append(mapping.get(word.charAt(i)));
        return mapped.toString();
    } else {
        return "";
    }
}
}

标签： javaalgorithmcryptographybacktracking

解决方案

主要问题似乎是您的程序无法解密（或使用）最后一行输入。发生这种情况是因为在您已经阅读了您将在该循环迭代中处理的行之后c.hasNextLine()评估循环条件。

此外，我观察到你解决了一个与挑战不同的问题，尽管是一个密切相关的问题。你应该

解密每一行

（强调添加），但你实际上做的是解密每一行的单词。输入描述不保证加密的行将没有前导或尾随空格，或者相邻单词之间不会有超过一个空格。如果其中任何一个发生，那么您的程序不会在其输出中重现它们。

此外，尽管我倾向于将问题描述理解为字典中的单词是单独存在的，没有任何前导或尾随空格，但如果实际上并非如此，那么您阅读它们的方法将包括它们的空格. trim()只需ing each on 输入就可以很容易地防止这种情况发生。

我最大的风格批评是这样的：不要在 loops 或ifor elseblocks的主体周围省略大括号，即使这些主体仅包含一个语句。这样做会使您的代码更难阅读，并为未来的维护者（包括未来的您）设置陷阱。在过去几年中，此类遗漏已成为至少一个备受瞩目的安全问题的原因。

推荐阅读