P1023 Mission 2 - A2 : Crack the Code! (HARD)

Problem Name: decodinghard

Easy Version Problem...

Problem Background

Merged with Problem Statement.

Problem Statement

Radar gets a message from WA State to TLE State. Because it's at war, the message is encoded. The encoding way is the Playfair Cipher, and we will show it for you:

• First, you'll get a keyword.

• Then, make every letter in the keyword unique in the keyword.

  • Put the left letters in the keyword one by one into a \(5 \times 5\) table.
  • Put the left letters in the alphabet(from a to z) into the table. (Remember that letters I and J share a grid.)

• For example, if the keyword is "AppOfficer and Radar" you'll get a table like this:

  A	P	O	F	I/J
  C	E	R	N	D
  B	G	H	K	L
  M	Q	S	T	U
  V	W	X	Y	Z

• Then it is the encoding.

  • Make the sentence(or phrase, word, etc.)'s letters in pair.
  • For each pair:
  • Find them in the table.
  • If the two letters are in the same row, the encoded letters are the two one grid on the right of each of them. (The last grid's right is the first grid in the row.) For example, CR becomes EN and GL becomes HB in the table above.
  • If the two letters are in the same column, the encoded letters are the two one grid under each of them. (The one under the last grid is the first grid in the column.) For example, FT becomes NY and WP becomes PE in the table above.
  • Otherwise, it is the two which make a rectangle with the original letters. For example, TR becomes SN, AZ becomes IV in the table above.
  • Note that if one letter becomes the letter grid I/J, we'll make it I.
  • Note that if the letters in the pair are the same, we just print the original letter with an additional x behind.
  • Note that if there’s only one letter in the pair, we just print that letter.

Now let's take on an example.

• Now the keyword is "AppOfficer and Radar", and the sentence we need to encode is "Radar would go back to class soon".
• First, create the cipher table. (The table is above.)
• Then, cut the sentence into pairs. That is, to cut it to "Ra da rw ou ld go ba ck to cl as ss oo n".
• Next, encode the pairs separately.
• The pairs after encoding is "Co ci ex is ul hp mc nb sf db om sx ox n".
• Put them together, we get "Cocie xisul hp mcnb sf dboms xoxn".

Radar wants to decode the message he got. We know the keyword and can you help Radar decode it?

Input

\(S\)

\(K\)

Here \(S\) is the encoded string and \(K\) is the keyword.

Output

\(O\)

Here \(O\) is the original string (the string decoded).

Constraints

This problem has partial points.

Note that \(|S|\) means the length of \(S\).

• For \(10\) points:
  • \(K=\text{“AppOfficer and Radar”}\);
  • \(S=\text{“Cocie xisul hp mcnb sf dboms xoxn”}\).
• For another \(20\) points:
  • \(K=\text{“A”}\).
• For all test cases and all points:
  • \(1 \le |K| \le 26\);
  • \(1 \le |S| \le 10^5\);
• Note that there might be both uppercase letters and lowercase letters in both \(K\) and \(S\).
• Note that it is guaranteed that there’re no x's in \(O\).

Samples

Input 1

Cocie xisul hp mcnb sf dboms xoxn
AppOfficer and Radar

Output 1

Radae eould go back to class soon