题解 | #字符串加解密#

字符串加解密

http://www.nowcoder.com/practice/2aa32b378a024755a3f251e75cbf233a

题意

给定字符串加密方法，和多行字符串

要求对“一行字符串加密，一行字符串解密”的输出每一行

加密规则：

数字字符循环右移

字母字符循环右移并改变大小转换

方法

利用ASCII和数学得到解密函数

先考虑加密

注意到，数字，小写字母，大写字母，分别在ASCII上连续，同时C++中的char直接参与加减运算时，会以其ascii的值为准

alt

那么我们可以利用这个性质，分别对数字，小写字母，大写字母，编写转换逻辑

对于解密

考虑数字：右移10位会得到本身，现在密文是右移了1位，所以只要再右移9位就能得到原文

考虑字母：（不考虑大小写的情况）右移26位会得到本身，现在是右移了一位，所以只要再右移25位就能得到原文

综上我们有了加密和解密的算法，实现即可。

代码

#include<bits/stdc++.h>
using namespace std;

char echar(char ch){ // 加密
    if('0' <= ch && ch<= '9'){ // 数字
        return (ch-'0'+1)%10+'0';
    }
    if('a' <= ch && ch<= 'z'){ // 小写字母
        return (ch-'a'+1)%26+'A';
    }
    if('A' <= ch && ch<= 'Z'){ // 大写字母
        return (ch-'A'+1)%26+'a';
    }
    return ch;
}

char dchar(char ch){ // 解密
    if('0' <= ch && ch<= '9'){
        return (ch-'0'+9)%10+'0';
    }
    if('a' <= ch && ch<= 'z'){
        return (ch-'a'+25)%26+'A';
    }
    if('A' <= ch && ch<= 'Z'){
        return (ch-'A'+25)%26+'a';
    }
    return ch;
}

int main(){
    string s;
    while(getline(cin,s)){ // 读入
        for(auto ch:s){ // 加密行
            printf("%c",echar(ch));
        }
        printf("\n");
        getline(cin,s);
        for(auto ch:s){ // 解密行
            printf("%c",dchar(ch));
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 我们读入所有字符，转换所有字符，转换的复杂度为常数，所以总时间复杂度为 $O(\sum |s_i|)$

空间复杂度: 主要消耗在读入字符串，所以空间复杂度为 $O (m a x (∣ s_{i} ∣))$

暴力解密

假设我们找不到解密的直接的逆函数。

那么我们至少知道，如果加密改变过字符，原字符是在数字和字母中的某一个

那么我们每次解密，可以枚举所有字母和数字，如果一个字母或数字的加密结果和密文相等，则找到原文

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<=b;i++)

char echar(char ch){ // 只有加密函数
    if('0' <= ch && ch<= '9'){
        return (ch-'0'+1)%10+'0';
    }
    if('a' <= ch && ch<= 'z'){
        return (ch-'a'+1)%26+'A';
    }
    if('A' <= ch && ch<= 'Z'){
        return (ch-'A'+1)%26+'a';
    }
    return ch;
}

int main(){
    string s;
    while(getline(cin,s)){
        for(auto ch:s){
            printf("%c",echar(ch));
        }
        printf("\n");
        getline(cin,s);
        for(auto ch:s){ // 解密
            bool found = false;
            rep(orich,'0','z'+1){ // 遍历所有字母数字
                if(echar(orich) == ch){ // 枚举找原文
                    printf("%c",char(orich));
                    found = true;
                    break;
                }
            }
            if(!found){
                printf("%c",ch);
            }
        }
        printf("\n");
    }
    return 0;
}