arrays - 在给定数组中查找整数序列

Question

我想知道是否有更好的方法(在我的实现正确的情况下)在给定数组中查找整数子序列。我已经使用 golang 实现了解决方案(如果这妨碍了审查，我可以使用不同的语言)。如果我没记错的话，下面的实现接近于 O(b)。

package main

import "fmt"

func main() {
    a := []int{1, 2, 3}
    b := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    r := match(a, b)

    fmt.Println("Match found for case 1: ", r)

    a = []int{1, 2, 3}
    b = []int{4, 5, 6, 7, 8, 9}
    r = match(a, b)

    fmt.Println("Match found for case 2: ", r)

    a = []int{1, 2, 3}
    b = []int{1, 5, 3, 7, 8, 9}
    r = match(a, b)

    fmt.Println("Match found for case 3: ", r)

    a = []int{1, 2, 3}
    b = []int{4, 5, 1, 7, 3, 9}
    r = match(a, b)

    fmt.Println("Match found for case 4: ", r)

    a = []int{1, 2, 3}
    b = []int{4, 5, 6, 1, 2, 3}
    r = match(a, b)

    fmt.Println("Match found for case 5: ", r)

    a = []int{1, 2, 3}
    b = []int{1, 2, 1, 2, 3}
    r = match(a, b)

    fmt.Println("Match found for case 6: ", r)

    a = []int{1, 2, 3, 4, 5}
    b = []int{4, 1, 5, 3, 6, 1, 2, 4, 4, 5, 7, 8, 1, 2, 2, 4, 1, 3, 3, 4}
    r = match(a, b)

    fmt.Println("Match found for case 7: ", r)

    a = []int{1, 2, 1, 2, 1}
    b = []int{1, 1, 2, 2, 1, 2, 1}
    r = match(a, b)

    fmt.Println("Match found for case 8: ", r)
}

func match(a []int, b []int) bool {
    if len(b) < len(a) {
        return false
    }

    lb := len(b) - 1
    la := len(a) - 1
    i := 0
    j := la
    k := 0
    counter := 0

    for {
        if i > lb || j > lb {
            break
        }

        if b[i] != a[k] || b[j] != a[la] {
            i++
            j++
            counter = 0
            continue
        } else {
            i++
            counter++
            if k < la {
                k++
            } else {
                k = 0
            }
        }

        if counter >= la+1 {
            return true
        }
    }

    return counter >= la+1
}

Answer 1

正确性

正如评论部分所讨论的，有一系列字符串匹配算法，通常分为单模式和多模式匹配算法。在您的情况下，它属于单一模式字符串匹配问题。

据我所知，最著名的算法是使用动态规划的 KMP 算法，以及一种名为 Rabin-Karp 的算法，它使用滚动哈希技术来加速该过程。两者都在 O(max(a,b)) 中运行。

但是，至少根据我的经验，您的代码与这些算法的正常实现不太相似。因此，我首先怀疑您的代码的正确性。您可以尝试像 a = {1, 2, 1, 2, 1}, b { 1, 1, 2, 2, 1, 2, 1 } 这样的情况，看看它没有给出正确的结果.

因此你可以

1. 放弃当前算法并学习那些标准算法，实现它们
2. 概述逻辑并草拟当前算法的证明，将其与那些标准算法背后的逻辑进行比较以验证其正确性

这部分留给你

复杂度

直接回答您的 OP:

不，O(max(a,b)) 是您在此问题中可以达到的最优值，这也是上述标准已知算法的复杂度。

我的理解是，它实际上是有道理的，因为在最坏的情况下，您必须至少读取较长字符串的每个字符 1 次。

您当前的算法显然也是 O(b)，因为您使用 i 从 0 循环到 b 的长度，无论您属于 i 的条件将增加 1，总计为 O(b)

---

因此复杂性实际上不是问题，正确性才是问题。