Vigenère密码

题意

给定 Vigenere 密钥和密文，解密得到原明文；密钥忽略大小写，输出保持密文位置的大小写。

思路

将密钥字母转成 $0$ 到 $25$ 的位移量。第 i 个密文使用 key[i % len(key)]，解密就是字母编号减去位移后模 26。根据密文字母大小写选择对应的 ASCII 基准值。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10key = input()
ciphertext = input()
plaintext = []

for index, encrypted in enumerate(ciphertext):
    shift = ord(key[index % len(key)].lower()) - ord("a")
    base = ord("A") if encrypted.isupper() else ord("a")
    plaintext.append(chr((ord(encrypted) - base - shift) % 26 + base))

print("".join(plaintext))

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/* author: Rainboy email: rainboylvx@qq.com  time: 2021年 12月 05日 星期日 10:53:29 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5,maxe = 1e6+5; //点与边的数量

int n,m;

char biao[200][200];

void init(){ 

    for(int i='a';i<='z';++i){ //行
        char start = i;
        for(int j='a';j<='z';++j){
            biao[i][j] = start;
            start++;
            if( start >'z')
                start = 'a';
        }
    }

    //for(int i='a';i<='z';++i){ //行
        //for(int j='a';j<='z';++j){
            //std::cout << biao[i][j] ;
        //}
        //std::cout << std::endl;
    //}

}

char mishi[10000];
char miwen[10000];
int len1,len2;

char to_lower(char c){
    if( c >='A' && c <='Z')
        return c-'A' +'a';
    return c;
}

// mishi miwen
char myfind(char a,char b){
    bool isBig = b >='A' && b <='Z';
    a = to_lower(a);
    b = to_lower(b);
    char duiying;
    for(int i = 'a' ;i<='z';i++){
        if( biao[i][a] == b){
            duiying = i;
            break;
        }
    }
    if(isBig)
        return duiying -'a' +'A';
    return duiying;
}

int main(int argc,char * argv[]){
    init();
    cin >> mishi;
    cin >> miwen;
    len1 = strlen(mishi);
    len2 = strlen(miwen);

    if( len1 < len2){ //copy
        for(int i =len1 ;i< len2;i++){
            mishi[i]= mishi[i-len1];
        }
    }
    for(int i=0;i<=len2-1;++i){
        std::cout << myfind( mishi[i], miwen[i]) ;
    }
    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

总结

循环密钥可由下标对密钥长度取模实现，无需真的扩展字符串。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结