朴素字符串匹配算法：比较次数统计及终止逻辑问题求助

原代码存在的两个核心问题 #

• 终止逻辑冗余：原代码中if i > len(T)-len(W): break完全多余，因为range(len(T) - len(W) + 1)已经限制了i的取值范围，i最大就是len(T)-len(W)，不会出现剩余文本长度不足的情况，直接删除即可。
• 比较次数统计错误：原代码只在匹配失败时加1次计数，匹配成功时加模式串长度，但忽略了匹配失败前已经完成的相等比较次数。正确的统计逻辑应该是每一次字符比较都计入总数，无论结果是相等还是不等。

修正后的代码 #

def search(W, T):
    count = 0
    len_W = len(W)
    len_T = len(T)
    
    # 提前处理模式串比文本长的情况，直接终止
    if len_W > len_T:
        print("模式串长度大于文本，无匹配可能")
        return
    
    # 循环范围确保剩余文本足够容纳模式串，无需额外终止判断
    for i in range(len_T - len_W + 1):
        j = 0
        while j < len_W:
            count += 1  # 每次字符比较都计数
            if T[i + j] != W[j]:
                break
            j += 1
        # 当j遍历完整个模式串，说明匹配成功
        if j == len_W:
            print(f"模式串在索引 {i} 处匹配，累计比较次数：{count}")
 
if __name__ == '__main__':
    T = "AABAACAADAABAAABAA"
    W = "AABA"
    search(W, T)

关键修改说明 #

1. 新增模式串长度校验：如果模式串比文本长，直接提示并返回，避免无效循环。
2. 移除冗余终止判断：利用range的范围限制，确保i的取值始终满足剩余文本长度≥模式串长度。
3. 修正计数逻辑：每次字符比较后立即给计数器加1，保证所有比较操作都被统计。
4. 优化输出格式：使用f-string让输出内容更易读。

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