Secret Word
A computer scientist has developed an encryption algorithm. This algorithm takes two inputs - one plain word and another, a key. Characteristics of inputs are as below.
Plain word: It is a string consisting of lowercase alphabets only.
Key: It is a set of pairs of strings consisting of lowercase alphabets only. For each pair, first string is the plain word and second string is its secret word. The characters of these secret words are jumbled but lengths of Plain Word and Secret Word are equal.
This algorithm finds the secret characters for each character in the inputted plain word by using the key. Then it combines all the secret characters in the same order to form a string called the secret word. Finally output this secret word. Below table shows how secret characters can be obtained from the key.
Your task is to help him in implementing the algorithm as a computer program.
Note: It is guaranteed that all characters in the given plain word can be converted to secret characters by using the given key.
Note: It is guaranteed that one plain text can be converted to only one encrypted text.
Constraints
1 <= P <= 52000
1 <= N <= 26
1 <= Length of a plain word in pair <= 50000
1 <= Length of a secret word in pair <= 50000
Length (plain word) == Length (secret word)
Input
First line contains string P denoting the plain text.
Second line contains an integer N denoting number of key pairs.
Next N lines, each contain two space separated strings denoting plain text and key.
Output
Print the encrypted word.
Time Limit
1
Examples
Example 1
Input
load
3
app lol
old tip
odd itt
Output
piot
Explanation
"load" is the plain word to be encrypted. Given Key contains 3 pairs of Plain word and Secret word combination. They are <"app", "lol">, <"old", "tip"> and <"odd", "itt">. From first pair, it's clear that the secret character of 'p' is 'l' and that of 'a' is 'o'. From third pair, it's clear that the secret character of 'd' is 't' and that of 'o' is 'i'. By using above findings, from second pair, it is clear that the secret character of 'l' is 'p'. Now we can build the secret word by replacing the characters of plain word by its corresponding secret characters as "piot".
Example 2
Input
a
1
a b
Output
b
Explanation
The word "a" is the plain word to be converted to secret word. The given key consists of only one plain word - secret word pair. i.e., <"a", "b">. From this, it is clear that the secret character of 'a' is 'b', since there is only one character in both secret and plain words. So, the final output is "b".
Plain word: It is a string consisting of lowercase alphabets only.
Key: It is a set of pairs of strings consisting of lowercase alphabets only. For each pair, first string is the plain word and second string is its secret word. The characters of these secret words are jumbled but lengths of Plain Word and Secret Word are equal.
This algorithm finds the secret characters for each character in the inputted plain word by using the key. Then it combines all the secret characters in the same order to form a string called the secret word. Finally output this secret word. Below table shows how secret characters can be obtained from the key.
Your task is to help him in implementing the algorithm as a computer program.
Note: It is guaranteed that all characters in the given plain word can be converted to secret characters by using the given key.
Note: It is guaranteed that one plain text can be converted to only one encrypted text.
Constraints
1 <= P <= 52000
1 <= N <= 26
1 <= Length of a plain word in pair <= 50000
1 <= Length of a secret word in pair <= 50000
Length (plain word) == Length (secret word)
Input
First line contains string P denoting the plain text.
Second line contains an integer N denoting number of key pairs.
Next N lines, each contain two space separated strings denoting plain text and key.
Output
Print the encrypted word.
Time Limit
1
Examples
Example 1
Input
load
3
app lol
old tip
odd itt
Output
piot
Explanation
"load" is the plain word to be encrypted. Given Key contains 3 pairs of Plain word and Secret word combination. They are <"app", "lol">, <"old", "tip"> and <"odd", "itt">. From first pair, it's clear that the secret character of 'p' is 'l' and that of 'a' is 'o'. From third pair, it's clear that the secret character of 'd' is 't' and that of 'o' is 'i'. By using above findings, from second pair, it is clear that the secret character of 'l' is 'p'. Now we can build the secret word by replacing the characters of plain word by its corresponding secret characters as "piot".
Example 2
Input
a
1
a b
Output
b
Explanation
The word "a" is the plain word to be converted to secret word. The given key consists of only one plain word - secret word pair. i.e., <"a", "b">. From this, it is clear that the secret character of 'a' is 'b', since there is only one character in both secret and plain words. So, the final output is "b".
Last edited on
If I understand the problem right, the encryption algorithm maps each plain text letter to a single encrypted letter. The "key" part of the input gives you clues to the mapping. If the key just told you the encrypted word for each plain word, it would be easy, but the encrypted words in the key have had their letters shuffled around.
To figure out the actual encryption mapping, you could do this:
do {
for each pair in the key
record how many times each uncracked letter occurs in the plain word and the secret word
if any uncracked letter occurs a unique number of times, then the plain letter must map to the secret one. Record that pair as a "cracked" letter.
}
} while (you cracked letters in this iteration)
Once you have the mapping, you can apply it to the plain word in the first part of the input.
Here's example 1 above:
Applying the algorithm:
PASS 1:
app lol: In the plain word, a occurs once and p occurs twice. In the secret word, 'o' occurs once and 'l' occurs twice. Since only 1 letter occurs once in the plain word (a) and the secret word (o), that means a maps to o. Similarly, p maps to l
old tip: Each letter occurs once so we don't know which maps to which.
odd itt: using the same logic as app->lol, we know that o maps to i and d maps to t.
Pass 2:
app lol: We know the mapping of all letters, so we can skip this
old tip: In pass 1, we learned the mappings of o and d, Since 'l' is the only unknown letter in the plain word and p is the only unknown letter in the secret word, l maps to p.
Pass 3:
app lol: all letters mapped.
old top: all letters mapped.
odd tip: all letters mapped.
No change in pass 3 so the loop exits.
To figure out the actual encryption mapping, you could do this:
do {
for each pair in the key
record how many times each uncracked letter occurs in the plain word and the secret word
if any uncracked letter occurs a unique number of times, then the plain letter must map to the secret one. Record that pair as a "cracked" letter.
}
} while (you cracked letters in this iteration)
Once you have the mapping, you can apply it to the plain word in the first part of the input.
Here's example 1 above:
load 3 app lol old tip odd itt |
Applying the algorithm:
PASS 1:
app lol: In the plain word, a occurs once and p occurs twice. In the secret word, 'o' occurs once and 'l' occurs twice. Since only 1 letter occurs once in the plain word (a) and the secret word (o), that means a maps to o. Similarly, p maps to l
old tip: Each letter occurs once so we don't know which maps to which.
odd itt: using the same logic as app->lol, we know that o maps to i and d maps to t.
Pass 2:
app lol: We know the mapping of all letters, so we can skip this
old tip: In pass 1, we learned the mappings of o and d, Since 'l' is the only unknown letter in the plain word and p is the only unknown letter in the secret word, l maps to p.
Pass 3:
app lol: all letters mapped.
old top: all letters mapped.
odd tip: all letters mapped.
No change in pass 3 so the loop exits.
Topic archived. No new replies allowed.