C++查找序列中指定长度回文的算法运行异常问题排查
代码逻辑错误排查与修复方案
核心错误点
- 数组越界访问:vector的下标范围是
0 ~ length-1,你内层循环的ri初始值设为length,直接访问ivec[ri]属于越界,会触发未定义行为。 - 循环变量被非法修改:你在内层
if分支里手动执行++i,而外层for循环本身每次迭代也会自动执行++i,会直接跳过多个下标,这就是你异常用例里i=1时本该触发的匹配没有执行的核心原因——i被多跳了一位直接到了3。 - 回文判定逻辑完全错误:
- 你当前的逻辑是全局遍历所有
i和ri的组合,找到相等值就计数,根本没有限定两个下标属于同一个待检查的子串区间,统计的相等值完全可能不属于同一个回文结构。 - 长度为
K的回文,左右边界的下标差应该为K-1,你写的std::abs(ri - i) <= K判定条件完全不符合回文长度要求。
- 你当前的逻辑是全局遍历所有
- 边界访问无校验:
ri == i分支里直接访问ivec[ri + 1]和ivec[i - 1],当i为0或者ri为length-1时会直接越界。
修复建议
如果你的需求是查找连续回文子串,推荐用更简单的中心扩展法,逻辑如下:
- 遍历每个下标作为回文中心,分奇数长度(中心为单个元素)、偶数长度(中心为两个元素)两种情况扩展。
- 扩展时检查左右字符是否相等,直到不相等为止,记录回文长度,若长度等于
K直接输出即可。
如果你的需求是查找不连续的回文子序列,需要用动态规划实现,状态定义为dp[i][j]表示序列下标i到j区间内最长回文子序列的长度,遍历所有区间找到长度等于K的即可。
内容的提问来源于stack exchange,提问作者Baron11
相关产品推荐
相关产品推荐

