本文主要是介绍POJ 2159 Ancient Cipher 杂题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:给定 str1, str2, 如果 str2 经过加密可以变成 str1。 输出YES,否则输出NO. 加密方式有两种,一种是改变字符,一种是调换顺序。
题解:这题还是耽搁了一会儿。一开始把题意理解错了,将substitution cipher (置换密码):当做按字典序偏移任意个位置。所以一直WR。
看了别人的解释:
“substitution cipher (置换密码):
Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different.For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from 'A' to 'Y' to the next ones in the alphabet, and changes 'Z' to 'A', to the message "VICTORIOUS" one gets the message "WJDUPSJPVT".
“移位”只是置换密码的一种,只要满足“Substitutes for all letters must be different.”就是置换了,比如
A->B
C->H
Z->D
对于这道题,input:
AAABB
CCCEE
应输出
YES
所以明文与密文的“字母频率的数组”应该是一样的,即明文中某字母出现8次,密文中也必须有某个字母出现8次。
所以字母种类,字母频率同时相等时,即被破解。
permutation cipher(排列密码):
Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation <2, 1, 5, 4, 3, 7, 6, 10, 9, 8> to the message "VICTORIOUS" one gets the message "IVOTCIRSUO".
明文随机排列,所以字母种类和频率都不变。
对于这道题,排列密码考虑和不考虑对解题无影响!”
#include <cstring>
#include <iostream>
using namespace std;
char first[101],second[101];
int frequency[2][30];
int main()
{
cin >> first >> second;
int i, j, counter;
int len = strlen(first);
for ( i = 0; i < len; i++ )
{
frequency[0][first[i]-'A']++;
frequency[1][second[i]-'A']++;
}
for ( i = 0; i < 26; i++ )
{
for ( j = 0; j < 26; j++ )
{
if ( frequency[0][i] == frequency[1][j] )
{
frequency[1][j] = -1; /* 当frequency[1][j] 被匹配过一次后,将其频率置为-1 */
break;
}
}
if ( j==26 ) break;
}
if ( i==26 )
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
这篇关于POJ 2159 Ancient Cipher 杂题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!