UESTC 1270 Playfair

Description

Playfair is a kind of substitution cipher.And the encryption role is simple.In general,there are three steps in Playfair algorithm.

Step 1: Creat a 5*5 secret key table.

Step 2:Tidy plaintext : only leave letters and omit others And if there are capital letters in the plaintext,change it into lower letters.

Step 3: Work out the ciphertext.

Now, let’s see an example.

Firstly,we should creat a 5*5 secret key table.Let’s assume that “ulysses” is the key.If there is a letter appearing more than once we should only retain the first one and delete the others.So we can get the real key “ulyse”.Then we will fill the secret key table with the key “ulyse” and with the other letters which haven’t appeared in the key “ulyse” in order(assume j is equal to i,so every element in the table is unique and j won’t be in this table).Finally, we will get a secret key table as follows:

Secondly,assuming that we will send a important message “balloon”.We should divide ballon into a few groups with exactly two letters.But if the two letters are the same,a single x will be inserted between the same two letters.So “balloon” will be divided into “ba” “lx” “lo” “on”.

Finally,we will encrypt the message.The substitution rules are followed:

1.If the group’s two letters are in the same row in the key table,each letter will be changed into the letter which is just on the right of it.(the first column is seen as on the right of the fifth column).

2.If the group’s two letters are in the same column in the key table,each letter will be changed into the letter which is adjacently below it.(the first row is seen as adjacent below fifth column).

3.If the group’s two letters are neither in the same row nor in the same column in the key table,each letter will be changed into the letter whose position is the same row as itself and the same column as another letter.

So “balloon” will be changed into “cbsvbvpo”.

Ps: j in the plaintext is equal to i and all the letter both in plaintext and ciphertext should be lower letter.And if there are capital letters in the plaintext,change it into lower letters.

Input

The first line will contain the secret key(no more than 25 letters). Then you will get a article(including capital letter and the lower letter).You should omit all the spacing , the punctuation and the numbers(maybe has two or more rows).If there are odd letters after tidying plaintext,delete the last letter.The article would end with a ‘*’.

Ps:You can assume that the article is no more than 10000 letters.And “xx” won’t exist. And the secret key only contains lower letters.

Output

The ciphertext which only includes lower letters.

Sample Input

cipher 
balloon 

Sample Output

dbspgsug

aespslsvqg

这题关键是理解题意，模拟操作过程就好了，需要注意的是对文本的处理，i和j是一样的

#include<iostream>  
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
const int size = 256;
int T, n, m, x[size], y[size];
char key[size][size];
char s[maxn], ati[maxn], ans[maxn];

void getkey()
{
	memset(x, 0, sizeof(x));
	memset(y, 0, sizeof(y));
	int tot = 1;
	for (int i = 0; s[i]; i++)
	{
		if (s[i] == 'j') s[i] = 'i';
		if (!x[s[i]] && !y[s[i]])
		{
			x[s[i]] = (tot - 1) / 5 + 1;
			y[s[i]] = (tot - 1) % 5 + 1;
			key[x[s[i]]][y[s[i]]] = s[i];
			tot++;
		}
	}
	for (char i = 'a'; i <= 'z'; i++)
	{
		if (!x[i] && !y[i])
		{
			x[i] = (tot - 1) / 5 + 1;
			y[i] = (tot - 1) % 5 + 1;
			key[x[i]][y[i]] = i;
			tot++;
		}
		if (i == 'i') x['j'] = x['i'], y['j'] = y['i'];
	}
	for (int i = 1; i <= 5; i++) key[6][i] = key[1][i], key[i][6] = key[i][1];
}

void get(char a, char b, char &c, char&d)
{
	if (x[a] == x[b]) { c = key[x[a]][y[a] + 1], d = key[x[b]][y[b] + 1]; return; }
	if (y[a] == y[b]) { c = key[x[a] + 1][y[a]], d = key[x[b] + 1][y[b]]; return; }
	c = key[x[a]][y[b]];	d = key[x[b]][y[a]];
}

int main(){
	//scanf("%d", &T);
	while (~scanf("%s", &s))
	{
		getkey();
		int tot = 0;
		while (~scanf("%s", &s))
		{
			for (int i = 0; s[i]; i++)
			{
				if (s[i] >= 'a'&&s[i] <= 'z') ati[tot++] = s[i];
				if (s[i] >= 'A'&&s[i] <= 'Z') ati[tot++] = s[i] + 32;
				if (s[i] == '*') goto solve;
			}
		}
	solve:
		int res = 0;
		char one, two;
		for (int i = 0; i < tot;)
		{
			if (i + 1 < tot)
			{
				if (x[ati[i]] == x[ati[i + 1]] && y[ati[i]] == y[ati[i + 1]])
				{
					get(ati[i], 'x', one, two);
					ans[res++] = one;
					ans[res++] = two;
					++i;
				}
				else
				{
					get(ati[i], ati[i + 1], one, two);
					ans[res++] = one;
					ans[res++] = two;
					++i; ++i;
				}
			}
			else break;
		}
		ans[res] = 0;
		printf("%s\n", ans);
	}
	return 0;
}