如何高效计算字符串列表拼接后目标子串的最大出现次数？

问题描述 #

给定一个字符串列表，将它们以任意顺序拼接成完整字符串后，求目标子串的最大出现次数。例如列表 ["pyooo", "fhriaha", "ppyhap"]、目标子串 "happy"，最优拼接结果 "fhriahappyhappyooo" 中该子串出现2次。

当前使用itertools.permutations枚举所有排列的方法效率极低，当字符串数量较多时完全无法运行，需要更高效的解决方案。

现有低效代码 #

from itertools import permutations

max_cnt = 0
words = ["pyooo", "fhriaha", "ppyhapp"]
target = "happy"
for i in permutations(words):
    cnt = ''.join(i).count(target)
    max_cnt = max(max_cnt, cnt)
print(max_cnt)

高效解决方案思路与实现 #

核心思路 #

1. 预处理单个字符串：先计算每个字符串内部包含的目标子串次数，同时记录每个字符串的前缀（长度为len(target)-1）和后缀（长度为len(target)-1）——只有相邻字符串的后缀+前缀才可能拼接出目标子串。
2. 状态转移式动态规划：用dp[mask][suffix_state]记录状态：mask是二进制掩码，表示已使用的字符串集合；suffix_state是拼接结果末尾长度为len(target)-1的子串；对应的值是当前状态下累计的最大目标子串次数。
3. 遍历更新状态：逐步尝试给每个状态添加未使用的字符串，计算新的累计次数（原有次数+新字符串内部次数+前后缀拼接产生的目标次数），并更新对应的新状态。

代码实现 #

def max_target_occurrences(words, target):
    target_len = len(target)
    if target_len == 0:
        return 0
    
    # 预处理每个单词：内部目标次数、前缀、后缀
    word_info = []
    for word in words:
        inner_cnt = word.count(target)
        # 取前缀：最多保留target_len-1个字符
        prefix = word[:target_len-1] if len(word) >= target_len-1 else word
        # 取后缀：最多保留target_len-1个字符
        suffix = word[-target_len+1:] if len(word) >= target_len-1 else word
        word_info.append((inner_cnt, prefix, suffix))
    
    n = len(words)
    # DP数组：dp[mask]是字典，键为后缀状态，值为当前最大次数
    dp = [{} for _ in range(1 << n)]
    
    # 初始化单个单词的状态
    for i in range(n):
        cnt, _, suffix = word_info[i]
        dp[1 << i][suffix] = cnt
    
    max_total = 0
    # 遍历所有掩码状态
    for mask in range(1 << n):
        current_states = dp[mask]
        if not current_states:
            continue
        # 尝试添加每个未使用的单词
        for i in range(n):
            if mask & (1 << i):
                continue
            cnt_i, prefix_i, suffix_i = word_info[i]
            # 遍历当前状态的所有后缀情况
            for prev_suffix, total in current_states.items():
                # 计算前后缀拼接产生的目标次数
                combined = prev_suffix + prefix_i
                cross_cnt = combined.count(target)
                new_total = total + cnt_i + cross_cnt
                # 计算新的后缀状态
                new_suffix = (prev_suffix + words[i])[-target_len+1:] if target_len > 1 else ""
                # 更新DP状态
                new_mask = mask | (1 << i)
                if new_suffix not in dp[new_mask] or new_total > dp[new_mask][new_suffix]:
                    dp[new_mask][new_suffix] = new_total
                    if new_total > max_total:
                        max_total = new_total
    
    # 兜底检查单个单词的最大次数
    for cnt, _, _ in word_info:
        if cnt > max_total:
            max_total = cnt
    
    return max_total

# 测试示例
words = ["pyooo", "fhriaha", "ppyhap"]
target = "happy"
print(max_target_occurrences(words, target))  # 输出2

效率对比 #

• 原方法时间复杂度为O(n! * L)，n是字符串数量，L是拼接后总长度，当n≥10时完全无法运行。
• 新方法时间复杂度为O(n² * 2ⁿ * K)，K是目标子串长度，当n≤20时都能高效运行，彻底解决原方法的性能瓶颈。

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