修改朴素搜索算法以允许容差

Question

我正在尝试 mod 以下天真的搜索功能，以查找在公差范围内的序列（每个数字可以是 +/- X%）。

这是我开始的地方：

Public Shared Function searchX(ByVal haystack As Byte(), ByVal needle As Byte())
        Dim M As Integer = needle.Length
        Dim N As Integer = haystack.Length

        For i As Integer = 0 To N - M
            Dim j As Integer

            For j = 0 To M - 1
                If haystack(i + j) <> needle(j) Then Exit For
            Next

            If j = M Then
                Return i
            End If
        Next
    End Function

因此，如果我正确理解了 Naive 算法的工作原理，则模式与我的数组的比较在行 If haystack(i + j) <> needle(j) Then Exit For 中完成。所以我这样改：

'根据拥有它的我的团队的要求删除了代码

我用不同的数组和模式测试了它，但现在看起来它只能找到一个“0”的序列；我错过了什么？我对这个算法的理解完全错误吗？更新：我对一些数据进行了最低限度的测试：

Dim haystack = New Byte() {&H0, &H1, &H2, &H3, &H4, &H5, &H6, &H7, &H8, &H9, &HA, &HB, &HC, &HD, &HE, &HF, &H1, &HF1, &HF4, &H3F, &H24, &HF4, &HF2, &HF4, &HF2, &H4F, &H2F, &H4F, &H2F, &H43, &HF2, &H4F, &H2F, &H4F, &H23, &H4F, &H23, &HF4, &HFF, &H42, &HF4, &HF3, &HF4, &H32, &HF4, &HF3, &H2F, &H4F, &H23, &HF0}
        Dim haystack2 = New Byte() {&H0, &H1, &H2, &H3, &H4, &H5, &H6, &H7, &H8, &H9, &HC, &HD, &HE, &HD, &HE, &HF, &H1, &HF1, &HF4, &H3F, &H24, &HF4, &HF2, &HF4, &HF2, &H4F, &H2F, &H4F, &H2F, &H43, &HF2, &H4F, &H2F, &H4F, &H23, &H4F, &H23, &HF4, &HFF, &H42, &HF4, &HF3, &HF4, &H32, &HF4, &HF3, &H2F, &H4F, &H23, &HF0}
        Dim needle = New Byte() {&HA, &HB, &HC}
        Dim tollerance = 20

在第一个 haystack 中使用针 A、B、C 和 tolerance=0 我应该在位置 10 和 none 在 hatstack2 中得到匹配。然后使用 tolerance = 20 我应该在两个 haystack 中的相同位置 10 找到一个匹配项，因为针的值仍在 20% 的 tolerance 中。

Answer 1

查看我对 For 循环的评论。

Private haystack As Byte()  = New Byte(){&H0, &H1, &H2, &H3, &H4, &H5, &H6, &H7, &H8, &H9, &HA, &HB, &HC, &HD, &HE, &HF, &H1, &HF1, &HF4, &H3F, &H24, &HF4, &HF2, &HF4, &HF2, &H4F, &H2F, &H4F, &H2F, &H43, &HF2, &H4F, &H2F, &H4F, &H23, &H4F, &H23, &HF4, &HFF, &H42, &HF4, &HF3, &HF4, &H32, &HF4, &HF3, &H2F, &H4F, &H23, &HF0}
Private needle As Byte() = New Byte() {&HA, &HB, &HC}
Private haystack2 As Byte() = New Byte() {&H0, &H1, &H2, &H3, &H4, &H5, &H6, &H7, &H8, &H9, &HC, &HD, &HE, &HD, &HE, &HF, &H1, &HF1, &HF4, &H3F, &H24, &HF4, &HF2, &HF4, &HF2, &H4F, &H2F, &H4F, &H2F, &H43, &HF2, &H4F, &H2F, &H4F, &H23, &H4F, &H23, &HF4, &HFF, &H42, &HF4, &HF3, &HF4, &H32, &HF4, &HF3, &H2F, &H4F, &H23, &HF0}
Public Shared Function searchXWithT(ByVal haystack As Byte(), ByVal needle As Byte(), ByVal err As Byte) As Integer
    Dim M As Integer = needle.Length
    Dim N As Integer = haystack.Length
    For i As Integer = 0 To N - M 'For i = 0 To 10
        For j = 0 To M - 1 'For j = 0 To 2
            If (CDbl(needle(j) - (needle(j) / 100 * err)) < CDbl(haystack(i + j))) And (CDbl(haystack(i + j)) < CDbl((needle(j) / 100 * err) + needle(j))) Then
            Else
                Exit For
            End If
        Next

        If j = M Then 'M will always be 3 and j can never be more than 2
            Return i 'i will never be returned
        End If
    Next
    Return 0
End Function

修改朴素搜索算法以允许容差

Modify naive search algo to allow tollerance

vb.net

algorithm

search