Kickstart 2020 RoundG A题C++代码提交后首测Runtime Error求排查
根本故障原因
- 无符号整数下溢触发非法内存访问
std::string::size()返回值为无符号类型size_t。当输入字符串长度≤4时,表达式text.size() - 4会发生无符号数下溢,得到一个远大于字符串实际长度的极大正数。此时for循环的边界条件i < text.size() - 4会持续成立,循环过程中会不断访问超出字符串内存范围的索引,直接触发段错误,即判题系统报出的Runtime Error。
尝试替换at()、substr()接口没有解决问题,是因为循环边界本身的逻辑错误没有被修正:无论用哪种接口访问元素,只要循环因为下溢进入了越界范围,就必然会触发非法访问。 - 循环边界过窄导致匹配漏判
就算输入字符串长度足够,原循环的终止条件也存在逻辑缺陷:
"KICK"是长度为4的子串,其合法起始索引最大为text.size() - 4(此时i+3刚好对应字符串最后一个有效字符);"START"是长度为5的子串,其合法起始索引最大为text.size() -5。原循环的终止条件为i < text.size() -4,意味着i最大只能取到text.size() -5,完全没有遍历到text.size()-4这个位置,会漏掉该位置可能出现的"KICK"匹配,导致统计的配对结果出现偏差。
修复方案
为了同时避免无符号下溢、覆盖所有合法匹配范围,需要先将字符串长度转换为有符号的64位整数(适配竞赛题目要求的大范围输入),再基于访问的合法性设置循环边界,直接通过索引偏移的范围判断替代容易下溢的无符号减法运算:
long long n = text.size(); long long open_count = 0; long long fragment_count = 0; // 循环覆盖所有可能出现"KICK"的起始位置:只要i+3不越界,就可完成KICK的匹配判断 for (long long i = 0; i + 3 < n; ++i) { // 判断当前位置是否为KICK的起始 if (text[i] == 'K' && text[i + 1] == 'I' && text[i + 2] == 'C' && text[i + 3] == 'K') { open_count++; } // 判断当前位置是否为START的起始:需先确认i+4不越界,再进行字符匹配 if (text[i] == 'S' && i + 4 < n && text[i + 1] == 'T' && text[i + 2] == 'A' && text[i + 3] == 'R' && text[i + 4] == 'T') { fragment_count += open_count; } }
注:原代码能通过官方样例测试,是因为样例输入的字符串长度较长,
text.size()-4计算得到的是正常正整数,没有触发下溢问题;且样例中的KICK位置都在循环遍历范围内,没有暴露漏判缺陷。但判题系统会覆盖短字符串、末尾匹配KICK等边界用例,因此会触发Runtime Error或结果错误。
内容的提问来源于stack exchange,提问作者AlephRZS
相关产品推荐
相关产品推荐

