M27371: Playfair密码

simulation, string, matrix, http://cs101.openjudge.cn/practice/27371/

Playfair密码是一种古典加密技术，它使用一个矩阵填充密钥和字母表中的其余字母，通常j被忽略，并被视为i。加密过程涉及将明文分成字母对，并对每对字母根据它们在矩阵中的位置进行加密，同样j也被视为i。

1. 密钥矩阵的生成

1.1 选择密钥：首先选择一个密钥，通常是一个单词或短语，如keyword。

1.2 填充矩阵：

去除重复字母：在密钥中去除重复出现的字母，只保留该重复字母出现的第一次进行填入。
填充密钥：将处理过的密钥填入矩阵的前几个格子，从左至右，从上至下填充。
填充剩余字母：在矩阵中填入字母表的其余字母。在传统Playfair密码中，通常将字母"j"视为字母"i"，以适应5x5矩阵的大小。

2. 加密过程

2.1 准备明文：将明文分成字母对。如果相邻字母相同就在该组的第一个字母后加入"x"后重新分组（如果第一个字母为"x"则加"q"）。如果明文处理后为奇数就在最后加入"x"（若最后一个字母为"x"则加"q"）。

2.2 对每个字母对进行加密：

同一行不同列：如果字母对位于矩阵的同一行，则每个字母都被替换为右侧的字母（最右边的字母替换为最左边的）。
同一列不同行：如果字母对位于矩阵的同一列，则每个字母都被替换为下方的字母（最下面的字母替换为最上面的）。
不同行和列：对于不在同一行或同一列的字母对，每个字母被替换为同一行中与另一个字母所在列相对应的字母。

3.示例：

假设密钥为keyword，明文为balloon。

密钥矩阵示例：

 k e y w o
 r d a b c
 f g h i(j) l
 m n p q s
 t u v x z

加密过程示例：

明文分组和填充：ba lx lo on。
加密：ba → cb，lx → iz，lo → sc，on → es。

因此，密文为cb iz sc es。

输入

第一行包含一个字符串，表示密钥。密钥只包含小写字母，长度不超过25。

第二行包含一个数字n，表示待加密明文数量。1 <= n <= 100。

接下来n行，每行为一个字符串，表示待加密的明文。明文只包含小写字母，长度不超过100。

输出

输出n行字符串，表示加密后的密文。

样例输入

Sample1 Input:
keyword
1
balloon

Sample1 Output:
cbizsces

样例输出

Sample2 Input:
java
3
likejava
programming
aaxx

Sample2 Output:
kaldavbv
qsnhqvrvkvsn
vwvwwr

解释：该样例密钥矩阵为
i a v b c
d e f g h
k l m n o
p q r s t
u w x y z

提示

tags: simulation，string，matrix

来源

2023fall pyn

关键在于：Playfair 密码中，j 实际上是不存在的。 你必须在任何逻辑（生成矩阵、判断重复、分组）开始之前，就把输入数据中的 j 全部抹杀变成 i。

逻辑：先转为 ii -> 发现重复 -> 插入占位符 -> 变成 ix，下一组处理剩余的 i。

引入一个 字典（HashMap） 来记录每个字母的坐标

python

import sys

def solve():
    # 1. 读取输入
    # 使用 sys.stdin.read 读取所有内容，处理多行输入更方便
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    key_input = input_data[0]
    n = int(input_data[1])
    plaintexts = input_data[2:]

    # 2. 生成密钥矩阵和坐标字典
    # 使用 list 保持顺序，set 用于去重辅助
    key = key_input.lower().replace('j', 'i')
    alphabet = "abcdefghiklmnopqrstuvwxyz" # 不含 j
    
    matrix_chars = []
    seen = set()
    
    # 填充 Key
    for char in key:
        if char not in seen:
            seen.add(char)
            matrix_chars.append(char)
            
    # 填充剩余字母
    for char in alphabet:
        if char not in seen:
            seen.add(char)
            matrix_chars.append(char)
            
    # 构建：矩阵 (5x5) 和 坐标映射 (char -> (row, col))
    # 优化点：用字典 pos_map 替代遍历查找
    matrix = [matrix_chars[i:i+5] for i in range(0, 25, 5)]
    pos_map = {char: (i // 5, i % 5) for i, char in enumerate(matrix_chars)}

    # 3. 定义加密函数
    def encrypt_text(text):
        text = text.lower().replace('j', 'i')
        res = []
        i = 0
        length = len(text)
        
        while i < length:
            a = text[i]
            b = ''
            
            # 尝试获取下一个字符
            if i + 1 < length:
                b = text[i+1]
                
                if a == b:
                    # 如果相同，插入填充字符，这一轮只消耗 text[i]
                    b = 'q' if a == 'x' else 'x'
                    i += 1 
                else:
                    # 如果不同，消耗 text[i] 和 text[i+1]
                    i += 2
            else:
                # 如果是最后一个字符，需要填充
                b = 'q' if a == 'x' else 'x'
                i += 1
            
            # 开始加密 a, b
            r1, c1 = pos_map[a]
            r2, c2 = pos_map[b]
            
            if r1 == r2: # 同行：右移
                res.append(matrix[r1][(c1 + 1) % 5])
                res.append(matrix[r2][(c2 + 1) % 5])
            elif c1 == c2: # 同列：下移
                res.append(matrix[(r1 + 1) % 5][c1])
                res.append(matrix[(r2 + 1) % 5][c2])
            else: # 矩形：取对角
                res.append(matrix[r1][c2])
                res.append(matrix[r2][c1])
                
        return "".join(res)

    # 4. 执行输出
    for text in plaintexts:
        print(encrypt_text(text))

if __name__ == "__main__":
    solve()

M27371: Playfair密码 ​

M27371: Playfair密码