Python如何拼接存在公共重叠子串的多个字符串？

核心实现思路 #

• 首先实现工具函数计算两个字符串的最大重叠长度：即前一个字符串的后缀与后一个字符串的前缀的最长公共子串长度
• 初始化拼接结果为列表第一个字符串，依次遍历剩余字符串
• 每轮计算当前拼接结果与待拼接字符串的最大重叠长度，将待拼接字符串去除重叠前缀后追加到结果末尾

完整代码实现 #

def get_max_overlap(str1: str, str2: str) -> int:
    # 最大可能的重叠长度为两个字符串的较短长度
    max_possible = min(len(str1), len(str2))
    # 从最长可能的重叠开始倒序验证
    for k in range(max_possible, -1, -1):
        if str1.endswith(str2[:k]):
            return k
    return 0

def merge_overlap_strings(str_list: list[str]) -> str:
    if not str_list:
        return ""
    # 若输入字符串带首尾空白可先执行strip处理
    result = str_list[0]
    for s in str_list[1:]:
        overlap_len = get_max_overlap(result, s)
        result += s[overlap_len:]
    return result

测试验证 #

输入示例：

ONESTRING
STRINGTHREE
THREEFOUR 
FOURFIVE

调用代码：

input_list = ["ONESTRING", "STRINGTHREE", "THREEFOUR ", "FOURFIVE"]
# 处理输入中的多余空格
input_list = [s.strip() for s in input_list]
print(merge_overlap_strings(input_list))

输出结果：

ONESTRINGTHREEFOURFIVE

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