求解EntwicklerHeld平台Transposition Cipher解密算法优化方案

核心优化思路：直接映射密文与明文的索引关系 #

不用构建0/1标记数组，也避免多次遍历开销，核心是推导密文每个字符对应的明文位置，直接完成字符定位与重组。

具体步骤 #

1. 计算每行的字符数量
   根据明文总长度n和行数rails，先算出锯齿排列中每行实际承载的字符数：

   • 首行/末行：每个周期（2*(rails-1)）含2个字符，总字符数为(n + period - 1) // period（period = 2*(rails-1)）；若rails=1则直接返回密文。
   • 中间行：每个周期含2个字符，总字符数为2*(n//period)，再根据余数调整：若n%period落在当前行的上下路径范围内，额外加1或2个字符。

2. 拆分密文到对应行
   依据第一步算出的每行长度，把密文分割成rails个片段，每个片段对应锯齿排列中的一行字符。比如密文cdnoig（rails=2）拆分后，第一行是cdno，第二行是ig。

3. 按锯齿路径重组明文
   模拟加密时的路径（向下→向上循环），依次从对应行取字符：

   • 初始化每行的字符指针，初始值为0；
   • 遍历明文的每个位置idx，计算该位置对应的行号：pos = idx%period，若pos<rails则行号为pos，否则为period-pos；
   • 根据行号从对应片段的指针位置取字符，指针自增，直到所有字符取完。

代码示例（Python） #

def decrypt_transposition(ciphertext, rails):
    n = len(ciphertext)
    if rails == 1:
        return ciphertext
    period = 2 * (rails - 1)
    
    # 计算每行的字符数
    row_lengths = []
    for i in range(rails):
        if i == 0 or i == rails - 1:
            count = (n + period - 1) // period
        else:
            count = 2 * (n // period)
            remainder = n % period
            if remainder > i and remainder < period - i:
                count += 1
            elif remainder >= period - i:
                count += 2
        row_lengths.append(count)
    
    # 拆分密文到各行
    rows = []
    start = 0
    for length in row_lengths:
        rows.append(list(ciphertext[start:start+length]))
        start += length
    
    # 按锯齿形读取明文
    plaintext = []
    pointers = [0] * rails
    for idx in range(n):
        pos = idx % period
        row = pos if pos < rails else period - pos
        plaintext.append(rows[row][pointers[row]])
        pointers[row] += 1
    return ''.join(plaintext)

# 测试用例
print(decrypt_transposition("cdnoig", 2))  # 输出: coding
print(decrypt_transposition("rn h oeaktecd", 2))  # 输出: rank the code

效率对比 #

• 原思路：三次遍历数组（构建标记、填充字符、读取明文），时间复杂度O(rails * n)；
• 优化方案：仅两次遍历（拆分密文、重组明文），时间复杂度O(n)，空间复杂度O(n)，行数越多时效率优势越明显。

内容的提问来源于stack exchange，提问作者CodingMan