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

Question

I would like to know if there is a better way (in the case my implementation is correct) to find a sub-sequence of integers in a given array. I have implemented the solution using golang (if this is an impediment for a review I could use a different language). If I am not mistaken the bellow implementation is close to 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

Correctness

As discussed in the comment section, there are a family of string matching algorithms, which normally categorized into single pattern and multiple pattern matching algorithm. In your case it belongs to single pattern string matching problem.

From my knowledge, the most well-known algorithm is KMP algorithm which uses dynamic programming, and an alternative named Rabin-Karp's algorithm which uses rolling hash technique to speed up the process. Both runs in O(max(a,b)).

However, your code is not very alike to these algorithm's normal implementation, at least to my experience. Therefore I suspect the correctness of your code at the first place. You can try cases like a = {1, 2, 1, 2, 1}, b { 1, 1, 2, 2, 1, 2, 1 } to see it is not giving correct result.

Therefore you can

1. Abandon current algorithm and learn those standard one, implement them
2. Outline the logic and sketch a proof of your current algorithm, compared it with the logic behind those standard algorithms to verify its correctness

I will leave this part to you

Complexity

To directly answer your OP:

No, O(max(a,b)) is the optimal you can achieve in this problem, which is also the complexity of the standard known algorithms mentioned above.

My understanding is that, it actually makes sense as at worst case, you HAVE TO read each character of the longer string at least 1 time.

Your current algorithm is also O(b) clearly, as you loop using i from 0 to length of b, and no matter which condition you fall into i will increase by 1, giving total O(b)

---

Therefore complexity is actually not the problem, the correctness is the problem.