统计二进制字符串中子序列出现次数，现有代码效率低如何优化？

你当前的代码存在两个核心性能瓶颈：

• 内层循环逐字符拼接字符串，Python中字符串是不可变对象，每次拼接都会生成新的字符串对象，内存和时间开销都很高
• 两层嵌套循环的时间复杂度为O(N*K)，N是原字符串长度，K是目标子串长度，数据量稍大就会出现明显的耗时上涨

另外注意：你描述中提到的是统计「子序列」，但你给出的示例和代码实际都是统计可重叠的连续子串的出现次数，子序列不需要字符连续，如果确实需要统计不连续的子序列，可以调整解法。

方案1：切片对比优化（简单快速，兼容原有逻辑） #

直接利用Python内置的字符串切片操作替换手写的字符拼接和内层循环，切片底层是C实现，性能远高于Python层的循环操作，代码也更简洁：

def subseq_uguale(stringa, testo, lunghezza):
    f = 0
    testo_len = len(testo)
    for i in range(testo_len - lunghezza + 1):
        if testo[i:i+lunghezza] == stringa:
            f += 1
    return f

这个版本的运行效率比你原来的代码高数十到上百倍，足以应对大部分普通场景。

方案2：KMP算法（超高性能，适合超大字符串场景） #

如果需要处理超长字符串或者长目标子串，可以用KMP匹配算法，时间复杂度可以降到O(N+K)，完全避免嵌套循环：

def subseq_uguale(stringa, testo, lunghezza):
    m = lunghezza
    n = len(testo)
    # 构建LPS部分匹配表
    lps = [0] * m
    prefix_len = 0
    i = 1
    while i < m:
        if stringa[i] == stringa[prefix_len]:
            prefix_len += 1
            lps[i] = prefix_len
            i += 1
        else:
            if prefix_len != 0:
                prefix_len = lps[prefix_len - 1]
            else:
                lps[i] = 0
                i += 1
    # 匹配计数
    count = 0
    i = 0  # 原字符串指针
    j = 0  # 目标子串指针
    while i < n:
        if stringa[j] == testo[i]:
            i += 1
            j += 1
        if j == m:
            count += 1
            # 回退指针支持重叠匹配
            j = lps[j - 1]
        elif i < n and stringa[j] != testo[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return count

内容的提问来源于stack exchange，提问作者Daniel Di Nella