字符串中寻找成簇模式（Clump）的Python代码错误排查求助

我正在解决一个编程问题，目标是找出字符串中的成簇模式（Clump），示例如下：

输入：
CGGACTCGACAGATGTGAAGAACGACAATGTGAAGACTCGACACGACAGAGTGAAGAGAAGAGGAAACATTGTAA
5 50 4
输出：
CGACA GAAGA

我使用了以下代码，但每次提交结果均显示错误，想请教代码是否存在问题，或是我对Clump相关概念理解有误？

def frequency_table(text, kmer_len):
    freq_map = {}
    nt = len(text)
    nk = kmer_len

    for i in range(0, nt-nk):
        pattern = text[i : i+nk]
        if not freq_map.get(pattern):
            freq_map[pattern] = 1
        else:
            freq_map[pattern] = freq_map[pattern] + 1
    
    return freq_map

def FindClumps(Text, k, L, t):
    Patterns = []
    n = len(Text)
    for i in range(n - L):
        Window = str(Text[i:L])
        freqMap = list(frequency_table(Window, k))
        for s in range(len(freqMap)):
            if len(freqMap[s]) >= t:
                Patterns.append(freqMap[s])

    return Patterns

问题分析与修正 #

首先明确Clump的定义：成簇模式指在长度为L的滑动窗口中，出现次数至少为t次的k长度子串（k-mer）。你的代码存在以下几个关键错误：

1. 滑动窗口截取错误

FindClumps函数中，Window = str(Text[i:L])是错误的——这会取从索引i到索引L的子串，窗口长度不固定（比如i=1时，窗口长度是49，不是要求的50）。正确的截取方式应该是Text[i:i+L]，确保每个窗口长度都是L。同时，循环范围range(n - L)会漏掉最后一个起始索引为n-L的窗口，应该改为range(n - L + 1)。

2. 频率表处理逻辑错误

frequency_table返回的是字典（键为k-mer，值为出现次数），但你用list(frequency_table(Window, k))只取了字典的键，后续判断len(freqMap[s]) >= t完全错误——这里freqMap[s]是k-mer字符串，长度固定为k，你应该判断该k-mer的出现次数是否≥t，而非字符串长度。正确的做法是遍历字典的键值对，检查计数。

3. 结果重复问题

同一个k-mer可能在多个窗口中满足条件，你的代码会重复添加到结果列表里，导致输出包含重复项，不符合示例要求。用集合存储结果可以自动去重。

4. k-mer遍历范围错误

frequency_table中的循环range(0, nt-nk)会漏掉最后一个k-mer（起始索引为nt-nk的子串），应该改为range(nt - nk + 1)。

修正后的代码 #

def frequency_table(text, kmer_len):
    freq_map = {}
    nt = len(text)
    nk = kmer_len
    # 修正循环范围，覆盖所有k-mer
    for i in range(nt - nk + 1):
        pattern = text[i:i+nk]
        # 简化计数逻辑
        freq_map[pattern] = freq_map.get(pattern, 0) + 1
    return freq_map

def FindClumps(Text, k, L, t):
    # 用集合自动去重
    Patterns = set()
    n = len(Text)
    # 修正窗口起始索引范围
    for i in range(n - L + 1):
        window = Text[i:i+L]
        freq_map = frequency_table(window, k)
        # 遍历键值对，检查出现次数
        for pattern, count in freq_map.items():
            if count >= t:
                Patterns.add(pattern)
    # 转成空格分隔的字符串，匹配示例输出格式
    return ' '.join(sorted(Patterns))

# 测试示例输入
text = "CGGACTCGACAGATGTGAAGAACGACAATGTGAAGACTCGACACGACAGAGTGAAGAGAAGAGGAAACATTGTAA"
k, L, t = 5, 50, 4
print(FindClumps(text, k, L, t))

运行修正后的代码，会输出符合要求的CGACA GAAGA。

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