修改朴素搜索算法实现容差匹配时的异常问题排查

看起来你在把精确匹配的朴素搜索改成带百分比容差的版本时遇到了逻辑问题，导致只有全0序列能匹配。我们先从核心匹配逻辑的常见错误点入手分析，再结合你的测试数据给出修正方案。

常见错误点分析 #

你提到修改了If haystack(i + j) <> needle(j) Then Exit For这一行——这确实是算法的核心，但在实现百分比容差时，有几个容易踩的坑：

1. 错误的容差计算逻辑（最可能的原因） #

百分比容差的核心是相对偏差，而非绝对偏差，很多人会在这里搞混计算方式：

• 正确的相对偏差判断：Math.Abs(haystackByte - needleByte) / needleByte <= tolerance / 100.0
• 但要注意两个边界情况：
  • 当needleByte = 0时，不能做除法，此时只有haystackByte = 0才符合容差（因为0的任何百分比偏差还是0）
  • 必须使用浮点数运算，避免VB整数除法截断小数导致的精度丢失

如果你的修改中出现以下情况，就会导致匹配异常：

• 用了整数除法（比如(haystack(i+j) - needle(j)) * 100 \ needle(j)），导致偏差计算严重不准
• 误把百分比容差当成绝对差值（比如允许±X而非±X%），对非0的needle值匹配条件要么过严要么过松
• 写反了判断逻辑（比如当符合容差时退出循环，而非不符合时退出）

2. 未处理无符号字节的数值范围 #

Byte类型是0-255的无符号整数，计算下限（比如needleByte * (1 - tolerance/100)）可能得到负数，这时候要把下限钳位到0，避免出现无效的数值范围。

3. 忽略浮点数精度误差 #

比如计算needleByte * 1.2时可能得到13.2这样的小数，而haystack的字节是整数，直接用范围判断可能出现精度问题，用相对偏差判断会更稳妥。

结合你的测试数据的修正方案 #

我们先写出正确的单字节容差判断逻辑，再整合到朴素搜索函数中：

第一步：单字节容差判断辅助函数 #

Private Shared Function IsWithinTolerance(haystackByte As Byte, needleByte As Byte, tolerance As Double) As Boolean
    If needleByte = 0 Then
        ' 0的容差只能匹配0
        Return haystackByte = 0
    End If
    ' 用浮点数计算相对偏差，避免精度丢失
    Dim relativeDiff As Double = Math.Abs(haystackByte - needleByte) / CDbl(needleByte)
    Return relativeDiff <= tolerance / 100.0
End Function

第二步：修改后的朴素搜索函数 #

Public Shared Function searchX(ByVal haystack As Byte(), ByVal needle As Byte(), ByVal tolerance As Double) As Integer
    Dim M As Integer = needle.Length
    Dim N As Integer = haystack.Length
    
    ' 边界处理：空needle或needle比haystack长，直接返回-1
    If M = 0 OrElse N < M Then
        Return -1
    End If
    
    For i As Integer = 0 To N - M
        Dim j As Integer
        For j = 0 To M - 1
            ' 替换原精确匹配为容差判断
            If Not IsWithinTolerance(haystack(i + j), needle(j), tolerance) Then
                Exit For
            End If
        Next
        ' 所有字节都符合容差，返回起始位置
        If j = M Then
            Return i
        End If
    Next
    ' 未找到匹配，返回-1
    Return -1
End Function

验证你的测试数据 #

我们来对应你的预期结果验证：

• 容差0%时：等价于精确匹配
  • haystack的位置10是&HA(10)，后续&HB、&HC也精确匹配，返回10
  • haystack2的位置10是&HC(12)，和needle第一个元素&HA(10)的相对偏差为20%，超过0%容差，返回-1
• 容差20%时：
  • haystack的位置10依然精确匹配，返回10
  • haystack2的位置10：
    • &HC(12) vs &HA(10)：相对偏差20%，刚好符合
    • &HD(13) vs &HB(11)：相对偏差≈18.18%，符合
    • &HE(14) vs &HC(12)：相对偏差≈16.67%，符合
      因此haystack2也会返回10，完全符合你的预期。

为什么你的修改后只能匹配全0序列？ #

最可能的原因是你在非0字节的容差计算上出了问题：

• 比如错误地使用整数除法导致相对偏差计算过大，使得非0字节永远不符合容差，只有0字节的判断逻辑是正确的
• 或者写反了匹配判断逻辑（比如当符合容差时退出循环），导致只有全0序列能意外满足所有字节的判断条件

对比上面的修正方案，你可以快速定位自己修改中的逻辑偏差。

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