UVA1339仿射和换位密码

news/2024/7/5 19:38:11 标签: 密码学

UVA1339

【题目描述】：密码

古典密码学有两种密码，仿射和换位，给定一段明文，一段密文，看密文能否由这段明文，是否可能通过仿射和换位得到。

【算法分析】：这道题目的关键是读题。因为接触过密码学，所以容易理解。

仿射密码：M=（m+a）%26，注意：对于相同的字母，仿射到同一个字母

换位密码：就是把所有的字母重排。

所以这道提的关键是，无论怎么仿射和置换，不用的字母总数不会增加，相同的字母的个数不会增加。即使通过很多次这样的操作也是这样。所以统计两段密文，不同的字母出现的个数，排序后比较即可。题外话：可能变换成功。

 1 //密码学：仿射密码和置换密码
 2 
 3 //难点：读题和归纳
 4 
 5 #include<iostream>
 6 
 7 #include<stdio.h>
 8 
 9 #include<string.h>
10 
11 #include<algorithm>
12 
13 #include<stdlib.h>
14 
15 #include<math.h>
16 
17 #include<queue>
18 
19 #include<vector>
20 
21 #include<map>
22 
23 #define MAXN 10+5
24 
25 #define MAXM 20000+5
26 
27 #define oo 9556531
28 
29 #define eps 0.000001
30 
31 #define PI acos(-1.0)//这个精确度高一些
32 
33 #define REP1(i,n) for(int i=0;i<=(n);i++)
34 
35 #define REP2(i,n) for(int i=1;i<=(n);i++)
36 
37 using namespace std;
38 
39 char s1[1005],s2[1005];
40 
41 int ap1[30],ap2[30];
42 
43 bool isok()
44 
45 {
46 
47     memset(ap1,0,sizeof(ap1));
48 
49     memset(ap2,0,sizeof(ap2));
50 
51     for(int i=0; s1[i]!='\0'; i++)
52 
53     {
54 
55         ap1[s1[i]-'A'+1]++;
56 
57         ap2[s2[i]-'A'+1]++;
58 
59     }
60 
61     sort(ap1,ap1+27);
62 
63     sort(ap2,ap2+27);
64 
65     for(int i=0; i<27;i++)
66 
67     {
68 
69         if (ap1[i]!=ap2[i]) return false;
70 
71     }
72 
73     return true;
74 
75 }
76 
77 int main()
78 
79 {
80 
81     while(cin>>s1>>s2)
82 
83     {
84 
85         if (isok()) cout<<"YES"<<endl;
86 
87         else cout<<"NO"<<endl;
88 
89     }
90 
91     return 0;
92 
93 }