C++实现子串最大连续出现次数统计函数返回异常排查

需求约束 #

仅允许使用基础字符串操作，实现字符串中指定子串的最大连续出现次数统计。

原有实现代码 #

int longest_str(std::string str, std::string dna) {
    int longest_count = 0;
    int current_count = 0;
    std::string temp;
    for (int i = 0; i <= (dna.size() - str.size()); ++i) {
      if (dna.at(i) == str.at(0)) {
          
        for (int j = i; j < i + str.size(); ++j) {
          temp.push_back(dna.at(j));
        }
        if (temp.compare(str) == 0) {
          current_count++;
          temp.clear();
          i += str.size();

      
        } else if (temp.compare(str) != 0) {
          if (current_count >= longest_count) {
            longest_count = current_count;
          }
          temp.clear();
          current_count = 0;
  
        } 
      } else if (dna.at(i) != str.at(0)) {
        if (current_count >= longest_count) {
          longest_count = current_count;
        }
        continue;
      }
        
  }
    
  return longest_count;
}

原设计逻辑 #

遍历DNA主串，索引i位置匹配到目标子串首字符时，截取从i开始、长度与目标子串相等的临时串做比对：

• 比对一致：当前连续计数+1，清空临时串，调整遍历索引后继续
• 比对不一致：清空临时串，更新历史最大连续计数，重置当前连续计数为0
• 未匹配到首字符：更新历史最大连续计数后继续遍历

测试用例 #

• 主串："GTATTAATTAATTAATTAGTA"
• 目标子串："ATTA"
• 预期输出：4

根因定位 #

代码返回结果异常来自4个逻辑漏洞，核心问题集中在计数更新、索引步进两个模块：

1. 索引步进多跳一位
   匹配成功时执行i += str.size()，但for循环每轮结束会自动执行++i，相当于一次匹配成功后直接跳过了str.size() + 1个字符。以测试用例为例，第一个ATTA起始索引为2，匹配成功后i被调整为6，经循环自增变为7，直接跳过了下一个ATTA的起始索引6，导致连续匹配被截断。
2. 末尾连续匹配丢失
   仅在匹配失败、遇到非首字符时更新longest_count，如果连续匹配刚好在主串末尾结束，循环终止时不会触发计数更新，直接返回会丢失这部分结果。
3. 非首字符分支未重置计数
   遍历到非首字符的分支中，只更新了最大计数，没有把current_count重置为0，中间间隔其他字符的匹配会被错误统计为连续匹配。
4. 无符号数运算越界风险
   dna.size()、str.size()返回值为无符号size_t类型，如果目标子串长度大于主串长度，二者相减会出现整数下溢，得到一个极大的正整数，导致循环越界访问内存触发异常。

修复方案 #

针对以上问题调整后的可运行代码如下：

#include <string>
#include <algorithm>

int longest_str(std::string str, std::string dna) {
    int str_len = static_cast<int>(str.size());
    int dna_len = static_cast<int>(dna.size());
    // 边界场景提前返回
    if (str_len == 0 || str_len > dna_len) {
        return 0;
    }

    int longest_count = 0;
    int current_count = 0;
    std::string temp;

    for (int i = 0; i <= dna_len - str_len; ++i) {
        if (dna.at(i) == str.at(0)) {
            temp.clear();
            for (int j = i; j < i + str_len; ++j) {
                temp.push_back(dna.at(j));
            }
            if (temp == str) {
                current_count++;
                // 步进值减1，抵消for循环自带的自增，避免漏匹配
                i += str_len - 1;
            } else {
                longest_count = std::max(longest_count, current_count);
                current_count = 0;
            }
        } else {
            longest_count = std::max(longest_count, current_count);
            current_count = 0;
        }
    }
    // 补做最后一次计数更新，覆盖末尾连续匹配的场景
    longest_count = std::max(longest_count, current_count);
    return longest_count;
}

该版本传入测试用例可正确返回4，覆盖了边界场景、漏匹配、计数错误等问题。

内容的提问来源于stack exchange，提问作者Anh Quân Võ