在给定的数组中找到一个整数序列。

huangapple go评论107阅读模式
英文:

Find a sequence of integers in a given array

问题

我想知道是否有更好的方法(在我的实现正确的情况下)来找到给定数组中的子序列。我已经使用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
}
英文:

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 &quot;fmt&quot;
func main() {
a := []int{1, 2, 3}
b := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
r := match(a, b)
fmt.Println(&quot;Match found for case 1: &quot;, r)
a = []int{1, 2, 3}
b = []int{4, 5, 6, 7, 8, 9}
r = match(a, b)
fmt.Println(&quot;Match found for case 2: &quot;, r)
a = []int{1, 2, 3}
b = []int{1, 5, 3, 7, 8, 9}
r = match(a, b)
fmt.Println(&quot;Match found for case 3: &quot;, r)
a = []int{1, 2, 3}
b = []int{4, 5, 1, 7, 3, 9}
r = match(a, b)
fmt.Println(&quot;Match found for case 4: &quot;, r)
a = []int{1, 2, 3}
b = []int{4, 5, 6, 1, 2, 3}
r = match(a, b)
fmt.Println(&quot;Match found for case 5: &quot;, r)
a = []int{1, 2, 3}
b = []int{1, 2, 1, 2, 3}
r = match(a, b)
fmt.Println(&quot;Match found for case 6: &quot;, 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(&quot;Match found for case 7: &quot;, r)
a = []int{1, 2, 1, 2, 1}
b = []int{1, 1, 2, 2, 1, 2, 1}
r = match(a, b)
fmt.Println(&quot;Match found for case 8: &quot;, r)
}
func match(a []int, b []int) bool {
if len(b) &lt; len(a) {
return false
}
lb := len(b) - 1
la := len(a) - 1
i := 0
j := la
k := 0
counter := 0
for {
if i &gt; lb || j &gt; lb {
break
}
if b[i] != a[k] || b[j] != a[la] {
i++
j++
counter = 0
continue
} else {
i++
counter++
if k &lt; la {
k++
} else {
k = 0
}
}
if counter &gt;= la+1 {
return true
}
}
return counter &gt;= la+1
}

答案1

得分: 1

正确性

如评论部分所讨论的,有一类字符串匹配算法,通常分为单模式和多模式匹配算法。在你的情况下,属于单模式字符串匹配问题。

据我所知,最著名的算法是KMP算法,它使用动态规划,还有一种叫做Rabin-Karp算法,它使用滚动哈希技术加速处理过程。这两种算法的时间复杂度都是O(max(a,b))

然而,你的代码与这些算法的常规实现并不相似,至少根据我的经验是这样的。因此,我首先怀疑你的代码的正确性。你可以尝试一些例子,比如 a = {1, 2, 1, 2, 1}, b { 1, 1, 2, 2, 1, 2, 1 },看看它是否给出了正确的结果。

因此,你可以:

  1. 放弃当前的算法,学习那些标准的算法,并实现它们。
  2. 概述你当前算法的逻辑,并提供一个证明,将其与那些标准算法的逻辑进行比较,以验证其正确性。

这部分我将留给你来完成。

复杂度

直接回答你的问题:

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

我理解的是,在最坏的情况下,你必须至少读取较长字符串的每个字符一次,这是有道理的。

你当前的算法显然也是O(b),因为你使用i从0到b的长度进行循环,无论你落入哪个条件,i都会增加1,总共需要O(b)的时间。


因此,复杂度实际上不是问题,问题在于正确性。

英文:

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.

答案2

得分: -1

由于您只需要一个序列,我建议将所有内容转换为字符串类型,并使用标准的strings包。

package main

import (
	"fmt"
	"strings"
)

func main() {
	fmt.Println(strings.Contains("1, 2, 3, 4, 5, 6, 7, 8, 9", "1, 2, 3"))
	fmt.Println(strings.Contains("4, 5, 6, 7, 8, 9", "1, 2, 3"))
	fmt.Println(strings.Contains("1, 5, 3, 7, 8, 9", "1, 2, 3"))
	fmt.Println(strings.Contains("4, 5, 1, 7, 3, 9", "1, 2, 3"))
	fmt.Println(strings.Contains("4, 5, 6, 1, 2, 3", "1, 2, 3"))
	fmt.Println(strings.Contains("4, 5, 6, 1, 2, 3, 2", "1, 2, 2, 3"))
	fmt.Println(strings.Contains("1, 2, 1, 2, 3", "1, 2, 3"))
}

Playground链接

英文:

Since you are only looking for a sequence, i would probably convert everything to string type and use the standard strings package.
Playground

package main
import (
&quot;fmt&quot;
&quot;strings&quot;
)
func main() {
fmt.Println(strings.Contains(&quot;1, 2, 3, 4, 5, 6, 7, 8, 9&quot;, &quot;1, 2, 3&quot;))
fmt.Println(strings.Contains(&quot;4, 5, 6, 7, 8, 9&quot;, &quot;1, 2, 3&quot;))
fmt.Println(strings.Contains(&quot;1, 5, 3, 7, 8, 9&quot;, &quot;1, 2, 3&quot;))
fmt.Println(strings.Contains(&quot;4, 5, 1, 7, 3, 9&quot;, &quot;1, 2, 3&quot;))
fmt.Println(strings.Contains(&quot;4, 5, 6, 1, 2, 3&quot;, &quot;1, 2, 3&quot;))
fmt.Println(strings.Contains(&quot;4, 5, 6, 1, 2, 3, 2&quot;, &quot;1, 2, 2, 3&quot;))
fmt.Println(strings.Contains(&quot;1, 2, 1, 2, 3&quot;, &quot;1, 2, 3&quot;))
}

huangapple
  • 本文由 发表于 2017年7月19日 12:38:06
  • 转载请务必保留本文链接:https://go.coder-hub.com/45181087.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定