基于记忆化实现Longest Common Substring最长公共子串提取

原代码核心问题 #

• 语法错误：getstring函数中出现非法变量名keºi1，且循环结构错误，核心逻辑写在while循环外会导致死循环
• 越界风险：getstring初始遍历指针取字符串长度，直接索引字符串会触发下标越界异常
• 逻辑缺陷：记忆化存储仅保存了最长长度，没有关联对应子串信息，回溯逻辑完全不符合状态匹配规则，无法正确提取子串

优化后实现 #

保留记忆化递归实现方案，调整记忆化存储结构，同时保存每个状态下的最长长度和对应子串，避免单独回溯的错误：

def memoization(s1, s2):
    mem = {}
    len1, len2 = len(s1), len(s2)

    def getKey(l1, l2, count):
        return f"{l1}|{l2}|{count}"

    def findLCS(l1, l2, count):
        key = getKey(l1, l2, count)
        # 递归终止条件
        if l1 == len1 or l2 == len2:
            return count, ""
        # 命中记忆化缓存直接返回
        if key in mem:
            return mem[key]
        
        current_match_str = ""
        # 当前字符匹配的情况
        if s1[l1] == s2[l2]:
            next_len, next_str = findLCS(l1 + 1, l2 + 1, count + 1)
            current_len = next_len
            current_match_str = s1[l1] + next_str
        else:
            current_len = count
        
        # 跳过s1当前字符的情况
        len2, str2 = findLCS(l1 + 1, l2, 0)
        # 跳过s2当前字符的情况
        len3, str3 = findLCS(l1, l2 + 1, 0)

        # 取三种情况的最大值对应的长度和子串
        max_len = max(current_len, len2, len3)
        if max_len == current_len:
            res = (current_len, current_match_str)
        elif max_len == len2:
            res = (len2, str2)
        else:
            res = (len3, str3)
        
        # 存入记忆化缓存
        mem[key] = res
        return res

    max_length, max_substr = findLCS(0, 0, 0)
    return max_length, max_substr

# 测试示例
s1 = "abcee12345"
s2 = "abcrd12345"
print(memoization(s1, s2)) # 输出 (5, "12345")

实现说明 #

• 记忆化缓存mem的键保持原有的l1|l2|count结构，值改为(最长长度, 对应子串)的二元组
• 递归过程中同时计算三种分支的长度和对应子串，每次取最大值存入缓存，无需单独做回溯提取子串的逻辑，避免逻辑出错
• 完全符合记忆化实现要求，避免了重复子问题的重复计算

内容的提问来源于stack exchange，提问作者Carlos García Hernández