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.
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.
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.
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.
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
Sample Output
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******
Есть подсказка
Does it pay to partition the words into equivalence classes based on repeated
letters and length?
Сделал вроде бы как правильное решение и достаточно быстрое для таких входных данных:
Code: Select all
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Collections.Specialized;
namespace __8_4
{
class Program
{
static string[] dict = new string[1];
static StringDictionary dictHash = new StringDictionary();
static void Main(string[] args)
{
string[] strLines = File.ReadAllLines("input.txt");
int currIndex = 0;
int dictAmount = int.Parse(strLines[currIndex++]);
dict = new string[dictAmount];
int i = 0;
while (i < dictAmount)
{
dict[i++] = strLines[currIndex++];
}
dictHash = GetDictHash(dict);
while (currIndex < strLines.Length)
{
Crack(strLines[currIndex++]);
}
Console.ReadKey();
}
static void Crack(string phrase)
{
string[] words = phrase.Split(' ');
StringDictionary sDic = GetDictHash(words);
Stack<string> inputWords = new Stack<string>();
StringDictionary dicNewPhrase = new StringDictionary();
foreach (string key in sDic.Keys)
{
inputWords.Push(key);
}
bool bRes = GetAssignment(inputWords, dicNewPhrase, phrase);
if (!bRes)
{
//Output *****
string strOutput = phrase;
for (int i = 0; i < strOutput.Length; i++)
{
if ((strOutput[i] != ' ') && (strOutput[i] != '*'))
strOutput = strOutput.Replace(strOutput[i], '*');
}
Console.WriteLine(strOutput);
}
}
static bool GetAssignment(Stack<string> inputWords, StringDictionary dicNewPhrase, string originalPhrase)
{
if (inputWords.Count == 0)
{
string strCkracked = Check(originalPhrase, dicNewPhrase);
//Output
if (!strCkracked.Equals(string.Empty))
{
Console.WriteLine(strCkracked);
return true;
}
else
{
return false;
}
}
string word = inputWords.Pop();
foreach (string key in dictHash.Keys)
{
if (word.Split(';')[0] == key.Split(';')[0])
{
dicNewPhrase.Add(word, key);
if (GetAssignment(inputWords, dicNewPhrase, originalPhrase))
{
//Found the original phrase
return true;
}
dicNewPhrase.Remove(word);
}
}
inputWords.Push(word);
return false;
}
static string Check(string inputPhrase, StringDictionary dicNewPhrase)
{
string phrase = inputPhrase;
string newPhrase = string.Empty;
//Building new phrase
string[] words = inputPhrase.Split(' ');
for (int i = 0; i < words.Length; i++)
{
if (newPhrase != string.Empty)
newPhrase += " ";
newPhrase += dictHash[dicNewPhrase[GetHash(words[i], i)]];
}
string ret = newPhrase;
for (int i = 0; i < newPhrase.Length; i++)
{
if (newPhrase[i] != '*')
{
if (phrase[i] == '*')
{
//Error here, current dictionary word represents replaced letter from other dictionary word
return string.Empty;
}
if (phrase[i] != ' ')
{
char charToReplace = phrase[i];
for (int j = i + 1; j < newPhrase.Length; j++)
{
if ((newPhrase[i] == newPhrase[j]) && (phrase[i] != phrase[j]))
return string.Empty;
}
phrase = phrase.Replace(phrase[i], '*');
newPhrase = newPhrase.Replace(newPhrase[i], '*');
}
}
}
return ret;
}
static string GetHash(string word, int index)
{
string strWordHash = string.Empty;
for (int i = 0; i < word.Length; i++)
{
int count = 0;
for (int j = 0; j < word.Length; j++)
{
if (word[i] == word[j])
count++;
}
strWordHash += count.ToString() + " ";
}
strWordHash += word.Length.ToString();
strWordHash += ";" + index.ToString();
return strWordHash;
}
static StringDictionary GetDictHash(string[] words)
{
StringDictionary sDic = new StringDictionary();
for (int wordIndex = 0; wordIndex < words.Length; wordIndex++)
{
string strWordHash = GetHash(words[wordIndex], wordIndex);
sDic.Add(strWordHash, words[wordIndex]);
}
return sDic;
}
}
}
Как можно оптимизировать решение? Можно ли избавиться от рекурсии. Если можно, то подкиньте, пожалуйста, идею.
