P1079 Vigenère 密码

calendar May 8, 2026 · 4 分钟阅读 · 模拟  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1079
难度 普及-（NOIP 2012 提高组）
知识点 字符串处理、密码学、模拟

题目描述

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。该密码曾在美国南北战争中为南军所广泛使用。

记密钥为 k，是一个字母串 k = k₁k₂…kₙ。

当明文 M = m₁m₂…mₙ 时，密文 C = c₁c₂…cₙ，其中 cᵢ = mᵢ ® kᵢ。

® 运算规则如下：

设 mᵢ 的字母表序号为 p，kᵢ 的字母表序号为 q（A/a = 0，B/b = 1，……，Z/z = 25），则： p ® q = (p + q) mod 26。

® 运算忽略大小写，但保持明文中字符的大小写形式。

密钥长度不足时循环使用。

本题给出密钥 k 和密文 C，要求还原明文 M。

输入格式

共 2 行：

  • 第一行：字符串 k（密钥），长度 ≤ 100，仅包含英文字母
  • 第二行：字符串（密文），长度 ≤ 1000，仅包含英文字母

输出格式

一个字符串，表示输入密钥和密文所对应的明文。

样例

输入

CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm

输出

Wherethereisawillthereisaway

解题思路

核心思想

本题本质是 Vigenère 密码的解密过程。

已知加密规则为 cᵢ = (pᵢ + qᵢ) mod 26，其中 pᵢ 为明文字母序号，qᵢ 为密钥字母序号，cᵢ 为密文字母序号。

将公式变形，得到解密公式：

pᵢ = (cᵢ - qᵢ + 26) mod 26

具体实现步骤：

  1. 依次遍历密文中的每个字符 m[i]
  2. 取 j = i % k.size()，实现密钥的循环使用
  3. 将密文字母 m[i] 和密钥字母 k[j] 都转为 0~25 的序号
  4. 套用解密公式计算明文字母序号，再转回字符
  5. 保持密文字母的大小写，明文相应位置输出同样大小写的字母

细节处理

  • 用三元表达式判断字符是大写还是小写：ch >='A' && ch <='Z'
  • 大写字母序号 = ch - 'A'，小写字母序号 = ch - 'a'
  • (mi - ki + 26) % 26 中的 +26 是为了避免负数

完整代码

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string k, m;
    cin >> k >> m;

    for (int i = 0; i < m.size(); i++) {
        int j = i % k.size();

        // 将密文和密钥字符转为 0~25 的序号
        int mi = (m[i] >= 'A' && m[i] <= 'Z') ? m[i] - 'A' : m[i] - 'a';
        int ki = (k[j] >= 'A' && k[j] <= 'Z') ? k[j] - 'A' : k[j] - 'a';

        // 解密：p = (c - k + 26) % 26
        int ci = (mi - ki + 26) % 26;

        // 保持原始大小写
        char ch = (m[i] >= 'A' && m[i] <= 'Z') ? ci + 'A' : ci + 'a';
        cout << ch;
    }
    return 0;
}

关键代码讲解

密钥循环

int j = i % k.size();

用取模运算实现密钥的无限循环。当密文长度超过密钥长度时，自然地回到密钥开头。

字母序号转换

int mi = (m[i] >= 'A' && m[i] <= 'Z') ? m[i] - 'A' : m[i] - 'a';

无论字符是大写还是小写，都转为 0~25 的数值，便于计算。® 运算本身忽略大小写。

解密公式

int ci = (mi - ki + 26) % 26;

由 cᵢ = (pᵢ + qᵢ) mod 26 推导得 pᵢ = (cᵢ - qᵢ + 26) mod 26。+26 保证被减数为正数，结果 mod 26 后必然落在 0~25 范围内。

大小写保持

char ch = (m[i] >= 'A' && m[i] <= 'Z') ? ci + 'A' : ci + 'a';

解密后的明文字母与密文字母保持大小写一致。

复杂度分析

方法 时间复杂度 空间复杂度
模拟 O(n) O(1)

其中 n 为密文长度。只需遍历一遍密文，每次 O(1) 计算，额外空间仅用于几个整数变量。

易错点

  1. 减法出现负数：直接 mi - ki 可能为负数导致字符编码错误，务必 +26 后再取模。
  2. 大小写不统一：密钥和密文中英文字母大小写混合，需要分别处理。
  3. 密钥循环：不要在密文遍历中直接用 i 作为密钥下标，应 i % k.size() 循环使用。

其他语言解法

Python

def main() -> None:
    k: str = input().strip()
    m: str = input().strip()

    result = []
    for i, ch in enumerate(m):
        j = i % len(k)

        mi = ord(ch) - ord('A') if 'A' <= ch <= 'Z' else ord(ch) - ord('a')
        ki = ord(k[j]) - ord('A') if 'A' <= k[j] <= 'Z' else ord(k[j]) - ord('a')

        ci = (mi - ki + 26) % 26
        base = 'A' if 'A' <= ch <= 'Z' else 'a'
        result.append(chr(ci + ord(base)))
        i += 1

    print(''.join(result))


if __name__ == '__main__':
    main()

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String k = br.readLine().trim();
        String m = br.readLine().trim();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m.length(); i++) {
            int j = i % k.length();

            int mi = Character.isUpperCase(m.charAt(i))
                    ? m.charAt(i) - 'A'
                    : m.charAt(i) - 'a';
            int ki = Character.isUpperCase(k.charAt(j))
                    ? k.charAt(j) - 'A'
                    : k.charAt(j) - 'a';

            int ci = (mi - ki + 26) % 26;
            char base = Character.isUpperCase(m.charAt(i)) ? 'A' : 'a';
            sb.append((char) (ci + base));
        }
        System.out.print(sb.toString());
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	var k, m string
	fmt.Fscan(in, &k)
	fmt.Fscan(in, &m)

	for i := 0; i < len(m); i++ {
		j := i % len(k)

		mi := toIndex(m[i])
		ki := toIndex(k[j])

		ci := (mi - ki + 26) % 26
		base := 'A'
		if m[i] >= 'a' && m[i] <= 'z' {
			base = 'a'
		}
		fmt.Printf("%c", rune(ci)+rune(base))
	}
}

// toIndex converts an ASCII letter to 0-25 index
func toIndex(b byte) int {
	if b >= 'A' && b <= 'Z' {
		return int(b - 'A')
	}
	return int(b - 'a')
}

JavaScript

'use strict';

/**
 * @param {string} k - 密钥
 * @param {string} m - 密文
 * @returns {string} - 明文
 */
function vigenereDecrypt(k, m) {
    let result = '';
    for (let i = 0; i < m.length; i++) {
        const j = i % k.length;
        const isUpper = m[i] >= 'A' && m[i] <= 'Z';

        const mi = isUpper ? m.charCodeAt(i) - 65 : m.charCodeAt(i) - 97;
        const ki = (k[j] >= 'A' && k[j] <= 'Z') ? k.charCodeAt(j) - 65 : k.charCodeAt(j) - 97;

        const ci = (mi - ki + 26) % 26;
        const base = isUpper ? 65 : 97;
        result += String.fromCharCode(ci + base);
    }
    return result;
}

const k = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')[0].trim();
const m = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')[1].trim();
process.stdout.write(vigenereDecrypt(k, m));