b983 - NOIP2012 Day1.1.Vigenère密码
題目描述
題目要求解 Vigenère 密碼加密後的密文，給定密文和密鑰，求出原始明文。Vigenère 密碼使用密鑰重複應用於明文的每個字符，並使用模 26 的加法進行加密。
解題思路
解題思路是實現 Vigenère 密碼的解密過程。首先，將密鑰擴展到與密文相同的長度。然後，遍歷密文的每個字符，根據密鑰的對應字符進行解密。解密公式為 明文字符 = (密文字符 - 密鑰字符 + 26) % 26。需要注意保持原始密文字符的大小寫。
複雜度分析
- 時間複雜度: O(n)，其中 n 是密文的長度。因為需要遍歷密文的每個字符一次。
- 空間複雜度: O(n)，其中 n 是密文的長度。因為需要擴展密鑰到與密文相同的長度，以及儲存一個布林陣列來記錄密文字符的大小寫。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string k,q;
cin >> k >> q;
while(k.length()<q.length()){
k+=k;
}
int ql=q.length();
bool a[ql];
for(int i=0;i<ql;i++){
if(q[i]>='A'&&q[i]<='Z'){
a[i]=1;
q[i]+=32;
}
else
a[i]=0;
if(k[i]>='A'&&k[i]<='Z'){
k[i]+=32;
}
}
char t;
for(int i=0;i<ql;i++){
if(a[i]==1){
t=(q[i]-k[i]+26)%26+'A';
}
else{
t=(q[i]-k[i]+26)%26+'a';
}
cout << t;
}
}