含多字母密钥的替换密码解密及所有拆分方案求解

问题背景 #

从某加密消息中解码得到如下明文片段，该消息采用含多字母密钥的替换密码，部分密钥的子串同时也是独立密钥，存在拆分歧义。采用长密钥优先的正则匹配解密时出现两处错误（NMH应为NEW，REVMR应为REVEL），因此需要实现通用解决方案：找出所有合法拆分方式，要求所有字符均被覆盖，拆分片段要么是字典中的密钥，要么不含任何密钥中的字符，最终输出所有合法拆分的列表。

加密明文片段 #

UAYUYAF FOY YIÆZYUA'W KYWLAJL.
YUAÆWY YIÆL FI' SUAYY YIÆLZLALK.
OYUAÆIRK FOY LYIO ÆJY.
ÆLLLAOLAIRÆFY LYYK, VGUAWGY IOÆLF.
UAYPHYIR LAL FOY KYWFUAGAFLAI'L I'S OLAW LAYIÆJY.
PGFAOYUA FOY YIÆZYUA. KYPHI'GUA OLAW AÆUAAÆWW.
UAYAIRÆLAYI IOOÆF IOÆW FÆZYL.

密钥字典 #

cipher = {
    "A": "C",
    "DE'": "X",
    "F": "T",
    "G": "U",
    "I'": "O",
    "IL": "Y",
    "IO": "W",
    "IR": "L",
    "J": "G",
    "K": "D",
    "KH": "Q",
    "L": "N",
    "LA": "I",
    "O": "H",
    "P": "B",
    "PH": "V",
    "S": "F",
    "U": "J",
    "UA": "R",
    "V": "P",
    "W": "S",
    "XU": "Z",
    "Y": "E",
    "YI": "M",
    "Z": "K",
    "Æ": "A",
}

原实现代码（存在内存溢出问题） #

from collections import Counter


def substring_tree(s: str) -> dict:
    d = {}

    def worker(s: str, dic: dict):
        for i in range(1, len(s) + 1):
            dic[s[:i]] = {}
            worker(s[i:], dic[s[:i]])

    worker(s, d)
    return d


def traverse_tree(tree, wordbank, keys, substrings=list()):
    result = []
    for k, v in tree.items():
        if k in wordbank and keys[k] < wordbank[k]:
            keys = keys.copy()
            keys[k] += 1
            if v:
                result.extend(traverse_tree(v, wordbank, keys, substrings + [k]))
            else:
                result.append(substrings + [k])
    return result


def all_construct2(target, wordbank):
    wordbank = Counter(wordbank)
    return traverse_tree(substring_tree(target), wordbank, Counter())

优化方案 #

原代码的核心问题是预先生成全量子串树，对于长度为N的字符串，子串树的节点数是O(N²)，当文本较长时会直接导致内存溢出。以下是针对性的优化实现：

优化后代码 #

from functools import lru_cache

def find_all_valid_splits(cipher_str, cipher_dict):
    # 预处理密钥：按长度降序排序，优先尝试长密钥以减少分支
    keys = sorted(cipher_dict.keys(), key=lambda x: -len(x))
    # 收集所有密钥的首字符，用于快速判断当前位置是否需要尝试密钥匹配
    key_first_chars = {k[0] for k in keys}

    @lru_cache(maxsize=None)
    def dfs(start_idx):
        # 递归终止条件：已处理完所有字符
        if start_idx == len(cipher_str):
            return [[]]
        
        valid_splits = []

        # 尝试匹配所有可能的密钥（长密钥优先）
        for key in keys:
            key_length = len(key)
            end_idx = start_idx + key_length
            if end_idx > len(cipher_str):
                continue
            # 检查当前子串是否匹配密钥
            if cipher_str[start_idx:end_idx] == key:
                # 递归处理剩余字符，拼接拆分结果
                for rest_split in dfs(end_idx):
                    valid_splits.append([key] + rest_split)
        
        # 处理非密钥字符：单个字符作为片段（符合"不含任何密钥字符"的要求）
        if start_idx < len(cipher_str) and cipher_str[start_idx] not in key_first_chars:
            for rest_split in dfs(start_idx + 1):
                valid_splits.append([cipher_str[start_idx]] + rest_split)
        
        return valid_splits

    # 启动递归，从字符串起始位置开始
    return dfs(0)

# 测试使用示例
if __name__ == "__main__":
    cipher = {
        "A": "C",
        "DE'": "X",
        "F": "T",
        "G": "U",
        "I'": "O",
        "IL": "Y",
        "IO": "W",
        "IR": "L",
        "J": "G",
        "K": "D",
        "KH": "Q",
        "L": "N",
        "LA": "I",
        "O": "H",
        "P": "B",
        "PH": "V",
        "S": "F",
        "U": "J",
        "UA": "R",
        "V": "P",
        "W": "S",
        "XU": "Z",
        "Y": "E",
        "YI": "M",
        "Z": "K",
        "Æ": "A",
    }
    # 取第一行文本测试
    test_text = "UAYUYAF FOY YIÆZYUA'W KYWLAJL."
    splits = find_all_valid_splits(test_text, cipher)
    print(f"共找到 {len(splits)} 种合法拆分方式")
    # 可打印部分结果查看
    print("部分拆分结果示例：")
    for split in splits[:3]:
        print(split)

优化核心点 #

1. 记忆化递归（动态规划）：使用lru_cache缓存每个起始位置的拆分结果，避免重复计算相同子问题，大幅降低递归次数和内存消耗。
2. 长密钥优先匹配：按密钥长度降序排序后尝试匹配，优先消耗长密钥，减少短密钥匹配导致的无效分支，同时符合多字母替换密码的常规解密逻辑。
3. 按需检查密钥：不预先生成所有子串，而是在递归时实时检查当前位置的子串是否匹配密钥，彻底避免了原代码中子串树的内存爆炸问题。
4. 高效处理非密钥字符：通过密钥首字符集合快速判断是否需要尝试密钥匹配，直接处理单个非密钥字符的拆分逻辑，减少不必要的分支。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος