#P4959. Vigenère密码

Vigenère密码

Vigenère密码

题目描述

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。该算法简单易用,破译难度较高,曾在战争中被广泛使用。

在密码学中,需要加密的信息称为明文,用 MM 表示;加密后的信息称为密文,用 CC 表示;密钥记为 kk。密钥是一个字母串 k=k1k2⋯kmk=k_1k_2\cdots k_m。当明文为 M=m1m2⋯mnM=m_1m_2\cdots m_n 时,密文为 C=c1c2⋯cnC=c_1c_2\cdots c_n,其中

ci=(mi+kj) mod 26c_i=(m_i+k_j)\bmod 26,j=((i−1) mod m)+1j=((i-1)\bmod m)+1。

加密时需要注意:

  • 运算忽略字母的大小写,并保持字母在明文 MM 中的大小写形式;
  • 当明文长度大于密钥长度时,将密钥 kk 循环重复使用。

例如,明文 M=HelloworldM=\mathrm{Helloworld}、密钥 k=abck=\mathrm{abc} 时,密文 C=HfnlpyosndC=\mathrm{Hfnlpyosnd}。

本题给出密钥和密文,要求还原明文。解密规则为:mi=(ci−kj+26) mod 26m_i=(c_i-k_j+26)\bmod 26,其中 j=((i−1) mod m)+1j=((i-1)\bmod m)+1,并保持密文字母的大小写形式。

输入格式

第一行是一个字符串,表示密钥 kk,长度不超过 100100,只包含大小写字母。

第二行是一个字符串,表示密文 CC,长度不超过 10001000,只包含大小写字母。

输出格式

输出一行,表示密文对应的明文。

数据范围与约定

1≤∣k∣≤1001 \le |k| \le 100,1≤∣C∣≤10001 \le |C| \le 1000;两个字符串均只含英文字母。

样例输入

CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm

样例输出

Wherethereisawillthereisaway

说明

测试数据为课程配套独立生成。